除魔卫道之降服树妖（树状数组）

       我最近越来越厉害了，树状数组都敢写了。嘿嘿

https://blog.****.net/djd1234567/article/details/47837185，原博客的链接加上我的一点点理解。

                                   

（从图例中可以看出每隔二的倍数就会出现加和，树状数组的下标是二的一倍也就是而就把数组a前两个相加，2的n次就把前2^n个相加，除去2的幂次点其余的偶数位都是a[n]+a[n-1]）                  

 

1 什么是树状数组
      

树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组A[1..n]，那么查询A[1]+...+A[n]的时，间是log级别的，而且是一个在线的数据结构。（说得好）

 

2 树状数组作用
      

        我们经常会遇到动态连续和查询问题，给定n个元素A[1~N]，让我们求sum[L,R] = A[L]+...+A[R]，或者更改A[i]的值。

       假设数据很小的时候，那么我们利用暴力就可以搞定，这个时候更改A[i]的复杂度为O(1)，但是求和的复杂度为O(n)，如果有m次求和就是O(n*m)，但是m很大的时候这个方法显然是不能够满足效率的要求。这个时候我们引入树状数组，树状数组的求和和更新都是O(logN)，所以大大的降低了复杂度。（说得对）

 

  3 具体分析

     1 建立树状数组就是先把A[] 和 C[]清空，然后假设有n个数那么就是做n次的update()操作就是建立树状数组，所以总的时间复杂度为O(nlogn)。

     2 设原数组为A[1..N]，树状数组为c[1..N]，其中c[k] = A[k-(2^t)+1] + ... + A[k]。比如c[6] = A[5] + A[6]。

        假设 A为被计数数组，C为树状数组（计数）

        0000 0001：C1 = A1
        0000 0010：C2 = A1 + A2
        0000 0011：C3 = A3
        0000 0100：C4 = A1 + A2 + A3 + A4
        0000 0101：C5 = A5
        0000 0110：C6 = A5 + A6
        0000 0111：C7 = A7
        0000 1000：C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
        ...
        0001 0000：C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8+ A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16

     3 也就是说，把k表示成二进制1***10000，那么c[k]就是A[1***00001] + A[1***00010] + ... + A[1***10000] 这一段数的和。

（这就是用lowbit的中心原理，也就解释了为什么用lowbit可以求出树状数组）

     4 设一个函数lowbit(k)为取得k的最低非零位，容易发现，根据上面的表示方法，从A[1]到A[k]的所有数的总和即为
        sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的时间内求出sum[k]。

 

     5 当数组中某元素发生变化时，需要改动的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 这个复杂度是logN (N为最大范围)

 

     6 如果题目要求sum[L , R] = sum[R]-sum[L-1]
        sum[L-1] = A[1]+A[2]+...+A[L-1]
        sum[R] = A[1]+A[2]+...+A[L]+...+A[R]
        sum[R]-sum[L-1] = A[L]+A[L+2]+...+A[R]

 

     7 树状数组的下标严格从1开始，所以如果出现0的情况要注意加1.(因为lowbit(0)是0所以如果出现为0的时候会进入无限循环中) , 树状数组中的每个元素至少含有它本身的一个值。

3  树状数组的两类操作

    1 单点更新，区间求和

       1 一维树状数组，单点更新，区间求和

       比如要更新点x ，x点的值加上val即调用add(x , val) ， 求区间[1 , x]的和即为getSum(x)

[cpp] view plaincopy

1.    
2. int lowbit(int x){  
3.     return x&(-x);  
4. }  
5.   
6. int getSum(int x){  
7.     int sum = 0;  
8.     while(x){  
9.         sum += treeNum[x];  
10.         x -= lowbit(x);  
11.     }  
12.     return sum;  
13. }  
14.   
15. void add(int x , int val){  
16.     while(x < MAXN){  
17.          treeNum[x] += val;  
18.          x += lowbit(x);  
19.     }  
20. }  

            2 二维树状数组，单点更新，区间求和

 

       比如要更新点(x , y) ，(x , y)点的值加上val即调用add(x , y , val) ， 求矩形[1 , 1] - [x , y]的和即为getSum(x , y)

            

            如上图求矩形的面积为getSum(x2 , y2)-getSum(x1-1,y2)-getSum(x2,y1-1)+getSum(x1-1 , y1-1)

           

[cpp] view plaincopy

1. int lowbit(int x){  
2.     return x&(-x);  
3. }  
4.   
5. int getSum(int x , int y){  
6.     int sum = 0;  
7.     for(int i = x ; i > 0 ; i -= lowbit(i))  
8.        for(int j = y ; j > 0 ; j -= lowbit(j))  
9.            sum += treeNum[i][j];  
10.     return sum;  
11. }  
12.   
13. void add(int x , int y , int val){  
14.     for(int i = x ; i < MAXN ; i += lowbit(i))  
15.        for(int j = y ; j < MAXN ; j += lowbit(j))  
16.            treeNum[i][j] += val;  
17. }  

 

 

 

    2 区间更新，单点求和  

         1 一维树状数组

        更改区间[x , y]，区间[x , y]里面的每个数全部加上val , 查询点k的值

        区间[x , y]加上val相当于点x加上val , 点y+1减去val，那么求k点的值就等于[1,k]的和

            

[cpp] view plaincopy

1. int lowbit(int x){  
2.     return x&(-x);  
3. }  
4.   
5. int getSum(int x){  
6.     int sum = 0;  
7.     while(x){  
8.         sum += treeNum[x];  
9.         x -= lowbit(x);  
10.     }  
11.     return sum;  
12. }  
13.   
14. void add(int x , int val){  
15.     while(x < MAXN){  
16.          treeNum[x] += val;  
17.          x += lowbit(x);  
18.     }  
19. }  
20.   
21. void solve(){  
22.     // 把区间[x , y]每一点加上val  
23.     add(x , val);  
24.     add(y+1 , -val);  
25.     // 计算点k的值  
26.     int num = getSum(k);  
27. }  

         2 二维树状数组

 

     更改矩形[x1 , y1] - [x2 , y2]，[x1 , y1] - [x2 , y2]里面的每个数全部加上val , 查询点(x , y)的值

          

          矩形[x1 , y1] - [x2 , y2]里面的每一个元素加上val相当于点(x1 , y1)加上val , 点(x1 , y2+1)减去val，点(x2+1 , y1)减去val ， 点(x2+1 , y2+1)加上val。那么求某个点(x , y)的值即求[1 , 1] - [x , y]的和

           

[cpp] view plaincopy

1. int lowbit(int x){  
2.     return x&(-x);  
3. }  
4.   
5. int getSum(int x , int y){  
6.     int sum = 0;  
7.     for(int i = x ; i > 0 ; i -= lowbit(i))  
8.        for(int j = y ; j > 0 ; j -= lowbit(j))  
9.            sum += treeNum[i][j];  
10.     return sum;  
11. }  
12.   
13. void add(int x , int y , int val){  
14.     for(int i = x ; i < MAXN ; i += lowbit(i))  
15.        for(int j = y ; j < MAXN ; j += lowbit(j))  
16.            treeNum[i][j] += val;  
17. }  
18.   
19. void solve(){  
20.      // 矩形[x1 , y1]-[x2 , y2]每个点加上val  
21.      add(x1 , y1 , val);   
22.      add(x2+1 , y1 , -val);   
23.      add(x1 , y2+1 , -val);   
24.      add(x2+1 , y2+1 , val);   
25.      // 求点(x , y)的值  
26.      int num = getSum(x , y);  
27. }  

 

 

5 常用的技巧

   假设初始化数组每个点的值为1，那么我们知道对于一维的树状数组来说，我们知道treeNum[i] = lowbit(i) . 对于二维树状数组来说treeNum[i][j] = lowbit(i)*lowbit(j)

    

[cpp] view plaincopy

1. void init(){  
2.     // 一维  
3.     memset(treeNum , 0 , sizeof(treeNum));  
4.     for(int i = 1 ; i < MAXN ; i++){  
5.         num[i] =1;  
6.         treeNum[i] = lowbit(i);  
7.     }  
8.       
9.     // 二维  
10.     memset(treeNum , 0 , sizeof(treeNum));  
11.     for(int i = 1 ; i < MAXN ; i++){  
12.        for(int j = 1 ; j < MAXN ; j++){  
13.            num[i][j] = 1;  
14.            treeNum[i][j] = lowbit(i)*lowbit(j);  
15.        }  
16.     }  
17. }  

那么问题来了

Problem D: 新年彩灯Ⅰ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 490  Solved: 62
[Submit][Status][Web Board]

Description

新年将至，YY准备挂一排彩灯，已知彩灯刚挂完的彩灯共有N盏（编号为1,2,3,……），并且都是灭的。彩灯的闪烁由一段程序控制。

每一秒钟程序会生成两个正整数a和b（1<=a,b<=N），然后将编号为a和b之间的所有灯的状态改变一次，即如果灯i是灭的，那么经过一次改变，灯i会亮，如果灯i是亮的，经过一次改变，灯i会灭。

 

当YY看着自己挂的彩灯不断闪烁的时候，问题来了，YY想知道任意时刻某一区间灯的状态。

 

Input

多组测试数据，每一组第一行是一个整数N（1<=N<=1000000）和一个整数M(1<=M<=3000)。

 

然后是M行数据，包括以下两种形式：

         1 a b 表示灯a和灯b之间的灯（含灯a和灯b）变换一次状态。

         0 x y 表示YY想知道此刻灯x到灯y（包含灯x和灯y）的状态.

 

Output

对于每次YY想知道结果的时候，输出一行灯的状态（编号小的灯优先），如果是亮的输出”1”，否则输出”0”;

 

Sample Input

3 3 1 1 2 1 2 3 0 1 3

Sample Output

101

思路：

           本以为是个青铜来给我送人头，没想到是个王者吊打我的屁股

          这题这么简单，一看就知道是树状数组啊，一遍读取输入一边对树状数组进行区间更新，最后进行单点查询，这么简单的题目还需要代码吗，我觉得不用。