树状数组模板很好写，但是不太好理解，主要是一些二进制的东西。 解决的问题：单节点更新，区间求和（虽然线段树都能办到，但是如果题目没有其他要求，这个还是比较好写且bug较少的） 树状数组是一个大佬发现的一种奇特的树（根据二进制搞的树），长下面这样 一，由图可知： c[1]=a[1]; c[2]=a[1]+a[2]; c[3]=a[3]; c[4]=a[1]+a[2]+a[3]+a[4]; c[5]=a[5]; c[6]=a[5]+a[6]; c[7]=a[7]; c[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]; 先别管它能干什么，你知道c数组是这样构成的就行，接着向下看。 二，先了解一下什么是lowbit(k)，它表示 k&-k ，它是位运算，它的运算结果是 把k的二进制的高位1全部清空，只留下最低位的1(如果一个数的二进制就一个1，那就是它本身)

//根据此图和这个代码好好体会一下lowbit #include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int main() { int n; while(~scanf("%d",&n)) { n= n&-n; printf("%d\n",n); } }

三，然后怎么构建c数组呢？ 观察图，你会发现a[1]会路过c[1],c[2],c[4],c[8],c[16], a[2]会路过c[2],c[4],c[8],c[16],a[3]会路过c[4],c[8],c[16], 然后你会发现不就是这样吗

//注意，与上面代码有一点不同 #include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int main() { int n; while(~scanf("%d",&n)) { n+= n&-n;//不同在这里 printf("%d\n",n); } }

那么构建c数组就是

#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int c[1000]; int n; void build(int index,int p) { while(index<=n) { c[index]+=p; index+=index&-index; } } int main() { while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { int a; scanf("%d",&a); build(i,a); } } return 0; }

四，最后一个问题了，怎么求和呢 再次找规律发现，依次向下减就能得到你想要得从0到k得和

#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int c[1000]; int n; void build(int index,int p) { while(index<=n) { c[index]+=p; index+=index&-index; } } int sum(int k) { int sum=0; while(k) { sum+=c[k]; k-=k&-k; } return sum; } int main() { while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { int a; scanf("%d",&a); build(i,a); } int x,y; scanf("%d%d",&x,&y); printf("%d\n",sum(y)-sum(x-1)); } return 0; }

最全板子

现在我这能理解到这个地步了，发现这个树的人真不错！ 学习链接：http://blog.csdn.net/qq_34374664/article/details/52787481 http://blog.csdn.net/qq_32680617/article/details/50867705 http://www.cnblogs.com/Penn000/articles/5758324.html