树状数组还是挺方便的，代码短功能也强大，完全可以用来替代一部分线段树的功能

有三种用法

一是对于单点更新，区间查询的

1 //hdu 1166 2 #include 
     
       3 #include 
      
        4 #include 
       
         5  6 using namespace std; 7  8 int n,t; 9 int a[50008];10 int tree[50008];11 12 void add(int x,int num)13 {14     while(x<=n)15     {16         tree[x]+=num;17         x+=x&-x;18     }19 }20 21 int read(int x)22 {23     int sum = 0;24     while(x)25     {26         sum+=tree[x];27         x-=x&-x;28     }29     return sum;30 }31 32 int main()33 {34     string tmp;35     int b,c;36     scanf("%d",&t);37     for(int j = 1;j<=t;j++)38     {39         memset(tree,0,sizeof(tree));40         scanf("%d",&n);41         printf("Case %d:\n",j);42         for(int i = 1;i<=n;i++)43         {44              scanf("%d",&a[i]);45              add(i,a[i]);46         }47 48         while(cin>>tmp,tmp!="End")49         {50             if(tmp=="Query")51             {52                 scanf("%d%d",&b,&c);53                 printf("%d\n",read(c)-read(b-1));54             }else if(tmp=="Add")55             {56                 scanf("%d%d",&b,&c);57                 add(b,c);58             }else if(tmp=="Sub")59             {60                 scanf("%d%d",&b,&c);61                 add(b,-c);62             }63         }64     }65     return 0;66 }
       
      
     

 

 

二是对于单点更新，但是查询区间最大最小值的

1 //hdu 1754 2 #include 
     
       3 #include 
      
        4 #include 
       
         5  6 using namespace std; 7  8 int n,m; 9 int a[200008];10 int tree[200008];11 12 int lowbit(int x)13 {14     return x&-x;15 }16 17 void update(int x)18 {19     while(x<=m)20     {21         tree[x]=a[x];22         for(int i=1;i
        
         <<=1)23             tree[x]=max(tree[x],tree[x-i]);24         x+=lowbit(x);25     }26     return ;27 }28 int query(int x, int y)29 {30     int ans = 0;31     while (y >= x)32     {33         ans = max(a[y], ans);34         y --;35         for (; y-lowbit(y) >= x; y -= lowbit(y))36             ans = max(tree[y], ans);37     }38     return ans;39 }40 41 int main()42 {43     char tmp;44     int c,d;45     while(scanf("%d%d",&m,&n)!=EOF)46     {47         memset(tree,0,sizeof(tree));48         for(int i = 1;i<=m;i++)49         {50             scanf("%d",&a[i]);51             update(i);52         }53         getchar();54         for(int i = 1 ;i <= n;i++)55         {56             scanf("%c%d%d",&tmp,&c,&d);57             if(tmp=='U')58             {59                 a[c] = d;60                 update(c);61             }62             else if(tmp=='Q')63             {64                 printf("%d\n",query(c,d));65             }66             getchar();67         }68     }69     return 0;70 }
        
       
      
     

 

 

三是对于区间更新，然后区间查询

这个区间更新主要是要用到一个差分数组

我们假设sigma(r，i)表示r数组的前i项和，调用一次的复杂度是log2(i)

设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]，那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到a[j](比如+v)，只需令c[i]+=v,c[j+1]-=v

这样c[i]->C[j]便会相当与加了j-i个v

怎么实现“区间修改，区间查询”呢？

观察式子：

a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n]) 

= n*c[1] + (n-1)*c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])  

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

=n*sigma(c,n) - sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询

 

1 //poj 3468 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #define Nmax 200008 6  7 using namespace std; 8  9 int n,m;10 long long a[200008];11 long long tree[200008];12 long long sum[200008];    //原始的前缀合13 long long c1[Nmax];   //前缀和14 long long c2[Nmax];   //前缀和*i-115 16 int lowbit(long long x)17 {18     return x&-x;19 }20 21 void add(long long *array,long long x,long long num)22 {23     while(x<=n)24     {25         array[x] += num;26         x+=x&-x;27     }28 }29 30 31 long long read(long long *array,long long x)32 {33     long long sum = 0;34     while(x)35     {36         sum += array[x];37         x-=x&-x;38     }39     return sum;40 }41 42 int main()43 {44     scanf("%d%d",&n,&m);45     char tmp;46     long long  l,r,q;47     for(int i = 1;i<=n;i++)48     {49         scanf("%lld",&a[i]);50         add(c1,i,a[i]-a[i-1]);51         add(c2,i,(i-1)*(a[i]-a[i-1]));52     }53     getchar();54     for(int i = 1;i<=m;i++)55     {56         scanf("%c",&tmp);57         if(tmp=='C')58         {59             scanf("%lld%lld%lld",&l,&r,&q);60             add(c1,l,q);61             add(c1,r+1,-q);62             add(c2,l,(l-1)*q);63             add(c2,r+1,-q*r);64         }else if(tmp=='Q')65         {66             scanf("%lld%lld",&l,&r);67             long long ans1 = (l-1)*read(c1,l-1)-read(c2,l-1);68             long long ans2 = (r)*read(c1,r)-read(c2,r);69             printf("%lld\n",ans2-ans1);70         }71         getchar();72     }73     return 0;74 }
       
      
     

 

 

四、利用树状数组来求第k小或者第k大

其主要的想法就是利用树状数组来统计每个数出现的次数

然后在通过枚举二进制的方式来进行统计，复杂度是log(n)

详情看代码理解

这个代码是第K大的，如果要求第K小的，那么枚举的时候反过来即可，以及判断条件改一下就OK

如果想取第几名的话，那么改插入的条件，每个值只能插入一次即可。

1 #include 
     
       2 #include 
      
        3 #define maxn 100000 4  5 int tree[maxn],n,k;    //tree是统计次数，每个数字出现的次数 6  7 int lowbit(int x) 8 { 9     return x&-x;10 }11 12 void add(int x, int num)13 {14     while (x <= maxn)15     {16         tree[x] += num;17         x += lowbit(x);18     }19 }20 21 int find(int k)     //找第k大22 {23     int cnt = 0, ans = 0;24     for (int i = 20; i >= 0; i--)       //枚举二进制数25     {26         ans += (1 << i);27         if (ans >= maxn|| cnt + tree[ans] >= k)     //如果ans超过最大值或者累加值加起来超过了k，那么说明这个位置的肯定在k的后面28             ans -= (1 << i);29         else30             cnt += tree[ans];     //说明第k肯定在ans的后面31     }32     return ans + 1;33 }34 35 void input() {36     memset(tree, 0, sizeof(tree));37     int t;38     scanf("%d%d", &n, &k);39     for (int i = 0; i