博主对于数据结构以及算法的学习修行尚浅，写博客更多的是为了日后的巩固与复习，博文中若是出现一些错误欢迎大家指出，O(∩_∩)O！
今天来介绍一下树状数组，作为一种重要的数据结构，它又有怎样的魅力； 提到树状数组，大家都会想到另一种数据结构——线段树； 关于线段树的内容，可以去看我的另一篇博客（线段树入门（c++）(≧∇≦)ﾉ）———>传送门 对于这两种数据结构，就像是一种父与子的关系：树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决； 既然如此，我们为什么还要学习树状数组呢？ 作为一种重要的数据结构，树状数组必然有着它自己的优势： 1.树状数组与线段树在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树. 2.代码简洁，容易理解，编程效率高；
传统数组的元素修改和连续元素求和的复杂度分别为O(1)和O(n)。树状数组通过将线性结构转换成伪树状结构（树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)，大大提高了整体效率。
对于树状数组的存储，既然是数组，自然只需要数组； 如图，上方的是树状结构，下面的数组是存储方式，至此，我们该如何通过树状结构构造所需要的树状数组呢？
树状数组的构造采取二进制思想； 假设数组a[1…16]，那么查询a[1]+…+a[16]的时间是log级别的，而且是一个动态的数据结构，支持随时修改某个元素的值，复杂度也为log级别。 来观察这个图： 令结点为A1…A16，C1…C16表示前缀和 可以得出 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(101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000) 查询过程每次就是去掉了二进制中的低位1(1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000) 查询过程就是修改过程反过来而已；
而现在的重点是如何取出二进制中的低位1；
c++与java库中没有这个函数，所以需要自己进行构造； 其中代码也非常简单，仅有一行；
int lowbit(int x){ return x&(-x);//取出二进制中的低位1 }既然有了取出低位1的方法，后续的操作也就变的简单起来；
修改值：
要将第x个元素加上k，不仅要修改tree [ x ]，还要修改所有覆盖到x的元素； 如图，若是要修改元素7，则覆盖的8与16都要进行修改；
void xiu_gai(int x,int k){//第x个元素加k while(x<=n){ tree[x]+=k;//修改 x+=lowbit(x);//找到下一个覆盖x的元素； } }求前缀和：
求前缀和即为查询操作，也就是将修改操作反过来而已；
int qiu_he(int x){ int sum=0; while(x){ sum+=tree[x]; x-=lowbit(x); } return sum; }求区间和：
都已经会求前缀和了，将区间右减去区间左就行了；
int y,z; cin>>y>>z; cout<<qiu_he(z)-qiu_he(y-1)<<endl;题出自luoguP3374（【模板】树状数组 1）https://www.luogu.com.cn/problem/P3374 题目描述： 数据范围： 样例说明：
典型的树状数组模板题（毕竟题目自己都说了(✿◡‿◡)）；
要点上面都说的差不多了，直接贴AC代码：
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int a[500005]; int tree[500005]; int n,m; int lowbit(int x){ return x&(-x); } void xiu_gai(int x,int k){ while(x<=n){ tree[x]+=k; x+=lowbit(x); } } int qiu_he(int x){ int sum=0; while(x){ sum+=tree[x]; x-=lowbit(x); } return sum; } int main() { cin>>n>>m; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ xiu_gai(i,a[i]); } int x,y,z; while(m--){ scanf("%d%d%d",&x,&y,&z); if(x==1){ xiu_gai(y,z); } else{ cout<<qiu_he(z)-qiu_he(y-1)<<endl; } } return 0; }