树状数组小结

退役好久了，惭愧的是一直没搞过树状数组和线段树，以前都是队友搞的，最近刷codeforeces被树状数组卡了好几次，遂决定怒刷树状数组。

0.算法

本来想写写长篇的算法过程，从如何建树到如何维护更新，结果发现这篇博客写的很赞了，我也就不写了，就写写个人对算法的理解以及刷的题目吧。
树状数组的优点就在于维护了一个前序和树，算法的核心就是『前序和』，碰到的各种题目也都是将各种模型转换为前序和，然后再进行查找和插入操作。
其时间复杂度如下：查找和插入/更新都是O(log MaxVal)，其中MaxVal表示树的最大下标，非常适合插入频繁的操作。以下read(x)表示查找x的前序和，update(x, p)表示更新x下标对应的数组的数值为p，以下BIT为表示树状数组的简称。
模板如下：

int tree[SIZE]; //BIT树  
int MaxVal; //下标最大值  
//查找下标为idx
int read(int idx) { // return value from 0-idx: c[idx]  
    int sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

//更新
void update(int idx, int val) { //update value at idx  
    while (idx <= MaxVal){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

int tree[SIZE][SIZE]; //2维BIT树  
int max_x, max_y; //二维下标最大值  
//二维更新
void update2D(int x , int y , int val){  
    int y1;
    while (x <= max_x){
        y1 = y;
        while (y1 <= max_y){
            tree[x][y1] += val;
            y1 += (y1 & -y1); 
        }
        x += (x & -x); 
    }
}

//二维查找
int read2D(int x, int y) {  
    int sum = 0;
    int y1;
    while (x > 0) {
        y1 = y;
        while (y1 > 0) {
            sum += tree[x][y1];
            y1 -= (y1 & -y1);
        }
        x -= (x & -x);
    }
    return sum;
}

1.poj 2352

题意：给定一堆星星的坐标，如果A星星在B星星的左下方（xa<=xb,ya<=yb），则A星星的level高于B，A星星最终的level的定义为比它小的星星的个数（比如有x个星星在A的左下方，则A的level为x），求每个level的星星的个数。
解题：对于所有星星，按y值升序排序，y相等则x升序，先遍历的level肯定不会大于后遍历的，对于每个星星，对其x值进行树状数组更新update(y, 1)，level则为read(x - 1)。

2.poj 1990

题意：一堆牛排成一列，每个牛有个坐标x和叫声p，两个牛i，j互相说话则采用最大的叫声max(p[i], p[j])，代价为max(p[i], p[j]) * abs(x[i] - x[j])，求所有牛两两通信的总代价和。
解题：直观的想法就是把牛按叫声升序排序，那么采用的叫声就是后面牛的叫声，那么，距离怎么搞？因为树状数组维持的前序和，所以我们得往那方面靠。把牛按叫声排序后，我们可以维护一个数组，对于位置pos，记录左边的比p[pos]小的个数nr和他们离坐标0的距离sum_left，那么对于pos牛，其左边的叫声代价和为：abs(x[pos]*nr-sum_left)*p[pos]；我们可以反向再扫一遍，记录右边比其小的牛的代价和，加起来就是最后的代价和。

3.poj 3067

题意：有一块大陆，最西边有n个城市（从北往南分别是1-n），最东边有m个城市从北往南分别是1-m），现需要在东西之间建k条高铁，高铁可能互相相交，求相交的交点的个数，注意：不会存在三个及三个以上的高铁交于一点，在城市相交不算相交。
解题：对于每一条高铁，按左端点降序，相同情况下右端点也降序（不能升序，否则前面的高铁右端点也加入read，然而在城市相交不算相交）。顺序遍历高铁，对右端点进行read和update即可。

4.poj 3468

题意：给定n个整数，q次查询和更新，对于每次查询(a,b)，输出[a,b]区间之和，对于每次更新(a,b,c)，更新[a,b]区间内每个数都加上c。
解题：若暴力更新必然超时，所以肯定不行。区间和包括两部分：一部分是sum[b] - sum[a-1]，若sum[x]表示的是从1-x的和，这部分比较好操作；另一部分是增量的部分，可以标记一个增量数组add，add[x]表示从x下标开始到n的增量，比如对于区间[a,b]的增量为c，则add[a]=c,add[b+1]=-c，表示从a开始到n都增加c，而从b+1开始到n都减上c，则b+1开始的部分增量刚好为0。对于点x，查找的操作是：

add[1]*x+add[2]*(x-1)+add[3]*(x-2)+...+add[x-1]*2+add[x]*1  
=segma(add[i]*(x-i+1)) {1<=i<=x}
=(x+1)*segma(add[i])+segma(i*add[i]) {1<=i<=x}

对于segma(add[i])和segma(i*add[i])维持两棵树状数组tree0和tree1进行处理：
查找(a,b)（左右都为闭区间，此处仅表示二元组而非开区间）的结果为：

ans = 0  
ans += sum[b] - sum[a-1] //初始和  
ans += (b+1) * read(tree0, b) - read(tree1, b) //右端点  
ans -= a * read(tree0, a - 1) - read(tree1, a - 1) //左端点

更新(a,b,c)的结果为：

update(tree0, a, c) //更新tree0的左区间  
update(tree0, b + 1, -c) //tree0的右区间  
update(tree1, a, a * c) //更新tree1的左区间  
update(tree1, b + 1, -(b + 1) * c) //tree1的右区间

5.poj 3928

题意：n个乒乓球运动员排成一列，每个运动员都有一个积分，两两运动会互相比赛，但需要一个裁判，裁判也在其他运动员之间选择，要求裁判的积分和位置都位于两位选手之间。问：总共可以举办多少场比赛？
解题：对于(a,b)运动员，需要裁判c，则一共就两种情况：a<=c<=b或者a>=c>=b。换位思考：我们对于每个c，找出前面比它小的个数*后面比他大的个数，以后前面比他大的个数*后面比他小的个数。搞一个数组，按位置排序，read和update积分。我们可以比较方便的求出前面比他小的个数，以及后面比他小的个数，那么前面比他大的个数只要坐标减去前面比他小的即可，同理后面比他大的个数。

6. 翻卡片问题

问题来源：here
题意：n个卡片放成一排，初始都为正面超下，两种操作：1.对[a,b]区间的牌翻过来，2.查找位置为x的牌的朝向。
解题：维持一棵BIT树对f求和，对于左端点a，update(a, 1)，右端点b，update(b + 1, -1)。那么对于每一点x，只要输出read(x) % 2即可，因为x若落在[a,b]右边，则其总和不变，落在[a,b]之内，总和+1，落在[a,b]左边，总和依旧不变，+1表示一次翻牌操作。

7.codeforces 365 Mishka and Interesting sum

题意：给定n个数，q次查询，对于每次查询[a,b]，返回[a,b]区间内所有出现次数为偶数的异或值。
解题：我们知道，对于出现次数为奇数次数的异或值只要把所有值异或起来就是最后的答案。然而，对于偶数次怎么搞？只要再异或上出现一次的个数即可。我们维持两个数组，sum1[x]记录从下标从1~x的所有数字异或值，这个不需要BIT就能搞；再需要一个异或只出现一次的数，这个可以用BIT来解决，update(pos, x)更新下标为pos的数为x，注意：此时用到的BIT不在是朴素的求和的方式，而是需要改成异或的方式。read(pos)返回到pos为止出现1次的数的异或值。那么什么时候update呢？
我们需要对查询离线处理，然后按右边界排序，i从0-n开始处理，对于出现一次的数更新最后面的位置，取消前面出现的位置。这个只需要对原来出现的位置update一次即可，然后对新的位置再update一次，老的位置由于两次异或重新置0。这样[a,b]区间内就能保留只出现一次的个数。

8.poj 1195

题意：给定二维矩阵，可能存在1.查找给定矩阵区间内的手机个数，2.更新某一点的手机个数。
解题：朴素的二维BIT，搞个模板就可以了。

9.poj 3321

题意：给定一棵树，每棵树的树杈和叶子位置上会长有果实，给定两种操作：查询（以当前节点为根，查找当前子树总的果子总和），更新（原来有果实的变成没果实，没果实的变成有果实）。
解题：对子树后序遍历重新编号，每个位置标记两个flag，第一个标号le为子树内最小的标号，第二个标号ri为最大的标号（也就是当前节点自己）。假设当前结点为x，那么，对于查询就是：read(x.ri) - read(x.le - 1)；对于更新就是：update(x.ri, 1 or -1)。
其实，一开始我尝试使用树状DP搞，开始遍历一遍构树，然后对于更新只需要向上更新至根即可，复杂度O(log(n))，对于查找直接输出O(1)就可以了，但一直超时。估计原因在于更新操作递归调用的过程，毕竟这是一道连开vector都会超时的题目。

10.poj 2155

题意：给定布尔型nxn数组，有两种操作：1.反转[(x1,y1),(x2,y2)]范围内的矩阵，2.查询(x,y)。
解题：这题基本和6. 翻卡片问题一致，唯一不同的就是扩张到二维，其方法一致，更新时如下：update(x1, y1, 1); update(x2 + 1, y2 + 1, -1); update(x1, y2 + 1, -1); update(x2 + 1, y1, -1);。

说明

装载请注明链接：http://vinllen.com/shu-zhuang-shu-zu-xiao-jie

参考

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
http://www.hawstein.com/posts/binary-indexed-trees.html
http://kenby.iteye.com/blog/962159

Your browser is out-of-date!

Vinllen Chen