士兵杀敌1（树状数组）

浏览数：30 / 时间：2015年06月08日

首先，要先讲讲树状数组：

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。

技术分享

假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。

来观察上面的图：

令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：

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

这里有一个有趣的性质：

设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，

所以很明显：Cn = A(n – 2^k + 1) + ... + An

算这个2^k有一个快捷的办法，定义一个函数如下即可：

1 int lowbit(int x)
2 {
3 
4 return x&(-x);
5 
6 }

当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：

step1:	令sum = 0，转第二步；
step2:	假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；
step3:	令n = n – lowbit(n)，转第二步。

 1 int Sum(int n)
 2 {
 3     int sum=0;
 4     while(n>0)
 5     {
 6          sum+=c[n];
 7          n=n-lowbit(n);
 8     }    
 9     return sum;
10 }

可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：

n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。

那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。

所以修改算法如下（给某个结点i加上x）：

step1:	当i > n时，算法结束，否则转第二步；
step2:	Ci = Ci + x， i = i + lowbit(i)转第一步。 i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。

代码如下：

1 void change(int i,int x)
2 {
3      while(i<=n)
4      {
5           c[i]=c[i]+x;
6           i=i+lowbit(i);
7      }
8 }

对于数组求和来说树状数组简直太快了!

参考资料：百度百科

好了，因此士兵杀敌1的题目代码可用树状数组求和：

代码出处

 1 #include"stdio.h"
 2 #include<string.h>
 3 int a[1000000];
 4 int main()
 5 {
 6         int n,sum;
 7         scanf("%d%d",&n,&sum);
 8         int i,j,k;
 9         memset(a,0,sizeof(a));
10         for(i=1;i<=n;i++)
11         {
12              int num;
13              scanf("%d",&num);
14              j=i;
15              while(j<=n)
16              {
17                     a[j]=a[j]+num;
18                     j+=j&(-j);
19              }
20         }
21         for(i=0;i<sum;i++)
22         {
23               scanf("%d%d",&k,&j);
24               int s1=0,s2=0;
25               k=k-1;
26               while(k>=1)
27               {          
28                    s1=s1+a[k];
29                    k-=k&(-k);
30                }
31                while(j>=1)
32                {
33                      s2=s2+a[j];
34                      j-=j&(-j);
35                }
36                printf("%d",s2-s1);
37                putchar(‘\n‘);
38          }
39          return 0;
40 }