浅说树状数组
树状数组树状数组作为信竞中又一个较为简洁的数据结构，也是非常的有用且好玩，虽然实用性没有线段树那么广，但是架不住它代码短啊！
引入
现在我们要维护一个数组，使其可以做修改和查询区间和。怎么做？
很显然，我们可以使用之前学过的分块来做，但是呢时间复杂度为 \(\cal O(n\sqrt n)\)，一旦我的 \(n\) 大于 \(10^6\) 不久寄了？那么我们怎么做呢？
查询
看到 \(10^6\) 这个数，是不是有一种直觉会用 \(\cal O(n\log n)\) 的算法，而看到 \(\log n\) 会想到什么？二叉树！对吧。那么对于一个区间，我们是不是就可以直接得到如下的图：（注：最后一排为我们要求的区间）
比如说我们要求区间的区间和，是不是只需要求节点2和节点6的值？这样是不是就会快很多？
但是我们会发现很多的值用不到，比如说我要求区间的区间和，我们完全没有必要去求节点5，我们只需要求节点2减去节点4的值是不是就可以了（类似于前缀和的思想）
又因为任意一个数都可以被唯一表示成一个二进制数，所以说我们就可以把一个前缀和分解成多个 \(2^n\) 大小的区间来表示。
例如：\(11=2^3+2^1+2^0\)，那么我们就可以这样表示：节点 \(x\) 的数组表示以 \(x\) 结尾，长度为 \(lowbit(x)\) 的区间和。
其中 \(lowbitx(x)\) 表示在二进制下的最后一个1的位数 \(k\) 和这个1后面的所有的0所组成 \(2^k\)，比如说 \(\because 10=(110)_2\therefore lowbit(10)=2\)。
而如何快速求 \(lowbit\) 呢？我们要从定义出发，很显然，我们将 \(x\) 取反再加1，就得到的 \(-x\) 的二进制数，我们发现，如果此时对这两个数做与运算的操作，我们就可以的到最后的1的位数，例如，\(6\) 的二进制编码是 \(110\)，全部取反后得到 \(001\)，加 \(1\) 得到 \(010\)。
\(proof:\) 设原先 x 的二进制编码是 (...)10...00，全部取反后得到 [...]01...11，加 1 后得到 [...]10...00，也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。
(...) 和 [...] 中省略号的每一位分别相反，所以 x & -x = (...)10...00 & [...]10...00 = 10...00，得到的结果就是 lowbit。
这样呢我们就可以用 \(\cal O(n)\) 的空间复杂度装下整个区间，而当我们要求一段区间和的时候，我们就可以用类似于前缀和的思想来进行操作。这样听起来是不是有一点抽象，我们可以画个图来感受一下：
比如说我们要求，我们实际上就是求-，而是 \(tree+tree=21+2=23\)，同时是 \(tree=14\)，那么就是 \(23-14=9\)。这个还是比较好理解的对吧，下面给出示范代码：
inline int lowbit(int x){
return x&(-x);
}
void query(int n){
int cnt=0;
while (n>0){
cnt+=tree;
n-=lowbit(n);//每一次取到当前管辖的范围
}
/*
也可以这样写
for (int i=n;i>0;i-=lowbit(i)){
cnt+=tree;
}
*/
return cnt;
}修改
我们现在可以完成查询的操作了，但是很显然，如果说我们只查询不修改的话，完全没有必要用树状数组，我们使用前缀和就可以很好的解决了，因此我们现在要看的是如何进行修改操作。很显然，我们的修改操作会分为两个部分，一个是单点修改，一个是区间修改。
单点修改
我们所要修改的，本质上就是寻找改变了一个值后，会影响的数组，也就是看这个点被哪些区间所管辖了。很显然，管辖 \(a\) 的 \(tree\) 一定包含 \(tree\)，那么我们每一次就网上跳一个 \(lowbit(x)\) 不久可以了吗？然后重复这个操作，直到超出了数组的范围停止。
下面给出示范代码：
inline void update(int x,int val){ while (xn; for (int i=1;i>a; } for (int i=n;i>=1;i--){ update(a); ans+=query(a-1); } couta,b=a; disc(); for (int i=1;i=1;i--){ update2(a,1); ans2=(n-i+1)-query2(a); } for (int i=1;irightint n,m;inline int lowbit(int x){ return x&(-x);}void update(int p,int x){ while (p0){ cnt+=tree; p-=lowbit(p); } return cnt;}int main(){ cin>>n>>m; for (int i=1;i>k>>l>>r; if (k==1){ update(l,0); update(r,1); }else { cout>a.y; a.x++,a.y++; maxn=max(maxn,a.y); } sort(a+1,a+1+n,cmp); for (int i=1;i
页:
[1]