树状数组介绍

一，前言

之前只会树状数组的一个区间求和，还是记得模板，这次在多校遇到一个用二维树状数组的题，就决心好好把树状数组搞一下，就发现树状数组有很多骚操作。

二，应用

1.树状数组的单点修改区间查询

这个是最常见的树状数组，我们很多书很多博客都是以这个作介绍，下面我也给大家讲一下，首先树状数组也是基于二分思想的，线段树是把一个区间以中间隔开

而树状数组是用一个神秘的操作，lowbit，也就是去当前这个数的最低位1，我们是以二进制1分开，又因为不同位置的1的大小不一样，所以我们分隔的区域也是不用

见下图

其中a数组就是原数组，c数组则是树状数组，可以发现

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

我们c数组的每个元素所掌管的区域是是  c[i]=a[i-2^k+1]....a[i]
k是末尾有几个0，也就是我们要找到最近的1，也就是区域大小是以最近的那个二进制1来决定，我们这样分开和二分有异曲同工之妙，
而且我们树状数组因为二进制的位数只有这么多位，所以每次最多循环这么多遍
是一个非常高效的数据结构

因为我们c[]每个都掌管一块区域如果我们要求1到n这个区间的和的话，只要把那几个区域的值加起来，也就是只加几次，其中不可能有重复的部分，这就是lowbit操作的好处/
所以我们求[1，7]的和只要 c[4] c[6] c[7],然后我们的求和操作
发现一个规律就是 7=111  6=110  4=100
每次少了最小的那个1，也就是树状数组的精髓，我也不好怎么用文字阐述，看代码，lowbit就是利用补码和原码之间的转换得到最低的那个1

int lowbit(x)
{
     return x&(-x);      
}
int sum(int x)
{
     int sum=0;
     while(x)
     {    
          sum+=c[x];
          x-=lowbit(x);
     } 
      return sum;       
}            

修改
我们想下，之前我们c[]里面都是一个区间的值，如果我们要修改一个点，那我们必须要把所有包括这个点的区间的值全部修改，又因为我们区间是递增的一种概念
只有更大的数才可能包含这个点嘛，所以我们要从当前的这个点从后面遍历

int lowbit(x)
{
     return x&(-x);      
}
void updata(int x，int num)
{
     while(x<=n)
     {    
          c[x]+=num;
          x+=lowbit(x);
     } 
}    

我们如果要求[l,r]区间的和，我们就只要利用前缀和思想sum(r)-sum(l-1)即可