树状数组专题

太过爱你忘了你带给我的痛 2022-07-16 13:16 87阅读 0赞

树状数组构造出的基础结构：

![这里写图片描述][883867-20160810150435699-1238857602.png]

树状数组的基础是一个被构造出来的式子:  
C\[i\]=A\[i\]+A\[i-1\]+….+A\[i-2^k+1\] k代表i的二进制的最后连续0的个数

如图：设节点编号为x，那么这个节点管辖的区间为2^k个元素。  
C1 = A1  
C2 = A1 + A2  
C3 = A3  
C4 = A1 + A2 + A3 + A4  
C5 = A5  
C6 = A5 + A6  
C7 = A7  
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8  
…  
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

--------------------

（1），lowbit

计算2^k有一个快捷的办法：

int lowbit(int x){
    return x&(x^(x–1));
    return x&(-x);//也可以写成这样
    }

（2），修改（Change）

i小于等于n的时候：  
c\[i\] = c\[i\] + x; // x为变化值，如3变成10,只需要修改10-3=7；  
i = i + lowbit(i)

若需改变a\[i\]，则c\[i\]、c\[i+lowbit(i)\]、c\[i+lowbit(i)+lowbit(i+lowbit(i)\]……也会发生改变

所以修改原数组中的第n个元素可以实现为:

void Change(int pos , int num)  //pos~n的数据修改num
    { 
        while(pos <= n) 
        { 
              in[pos] += num; 
              pos += Lowbit(pos); 
        } 
    }

（3），求和（Sum）

i大于0：  
sum = sum +c\[n\]; //从n开始往下回溯  
n = n - lowbit(n); // 每次查询下面节点

若需查询s\[i\]，则c\[i\]、c\[i-lowbit(i)\]、c\[i-lowbit(i)-lowbit(i- lowbit(i))\]……就是需要累加的c数组中的元素。

所以求和原数组中的第n个元素可以实现为:

int Sum(int n) 
    { 
        int sum = 0; 
        while(n > 0) //倒序相加
        { 
            sum += in[n]; 
            end -= Lowbit(n); 
        } 
        return sum; 
    }

（1），快速查询任意位置的和，sun(i)，  
（2），快速查询 i~j 区间的和，sum(j)-sum(i-1)：

![这里写图片描述][20161118215055790]

（3），如果是2维：查询（x1,y1），( x2,y2 )区间的和：

![这里写图片描述][20161118215848715]

（四）应用

（1），区间更新，单点求值  
（2），单点更新，区间求职  
（3），逆序数

--------------------

1，HDU 1166(敌兵布阵)  
2，NYOJ 116(士兵杀敌)  
[http://blog.csdn.net/acm\_hmj/article/details/53224105][http_blog.csdn.net_acm_hmj_article_details_53224105]  
3，HDU 1892(See you~~)

[883867-20160810150435699-1238857602.png]: /images/20220715/1b4ceba7bd6c48f796603e2823d43be6.png
[20161118215055790]: /images/20220715/57f2d7eebb8745b8a18b1681b75f45c7.png
[20161118215848715]: /images/20220715/f9dde6b7810c438cb3a03fa53027a27e.png
[http_blog.csdn.net_acm_hmj_article_details_53224105]: http://blog.csdn.net/acm_hmj/article/details/53224105