树状数组，顾名思义，长得像树的数组（然而并不是）

 注：图中AA数组表示各个数，CC数组表示一个区间的和

图中的C_iCi​，即CC数组下面的方框内的数字表示的是该下标对应的二进制值

那么为什么要这么做呢？

诸君请看

有上面这张图，我们知道，CC数组表示的是区间和， 而CC数组各个元素所包含的区间的长度却不尽相同，那么，规律是——

设C_iCi​中ii可以分解为i=2^k*bi=2k∗b,则ii决定了该数组元素所表示的区间和的区间长度(有点绕hhhh）

那么我们怎么获取其下标中所含2的个数呢？

现在 是时候让BOSS上场了！

int lowbit(int k)
{
    return k&(-k);
}

啊这。。。 这什么玩意儿？这按位与有什么用？

现在，让我们做个运算：假设k=14k=14 ，那么 kk作为一个整型变量，它占用了8个字节， 它的源码可以表示为：

| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |

\texttt{第一位是符号位，表示正负（0为正，1为负）}第一位是符号位，表示正负（0为正，1为负）

它的反码，补码都和它的源码相同；

它的相反数的源码为：

| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |

反码为：

| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |

补码为：

| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |

它和它的相反数的补码进行按位与后结果为：

| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

即：2

是不是很神奇？ 14刚好等于2^1*721∗7

这样，利用这个lowbitlowbit函数，我们便可以轻易地获取包含a_iai​的所有c_ici​

然后，进行修改和查询的代码便油然而生了：

void add(int pos,int a)//单个修改
{
    for(register int i=pos;i<=n;i+=lowbit(i))
    c[i]+=a;
}

int query(int pos)//求前pos个数的总和
{
    int summ=0;
    for(register int i=pos;i>0;i-=lowbit(i))
    summ+=c[i];
    return summ;
}

这样 我们就可以利用queryquery函数进行区间查询了，具体做法和前缀和极为相似

ans=query(z)-query(y-1)//求y到z的和

如果要区间修改呢？

这就需要差分的知识：

假设现在我们有一个差分数组ss,要将区间(i,j)(i,j)中的所有元素加上nn，可以转化为将元素s_isi​加上nn，元素s_{j+1}sj+1​减去nn

代码实现如下

add(i,a);
add(j+1,-a);//将i到j的区间加上a

这样，经过整合，我们可以得到完整代码（ P3374 【模板】树状数组 1 ）

#include <bits/stdc++.h>
using namespace std;
int c[500005],a,n,m,x,y,z;
int lowbit(int k)
{
    return k&(-k);
}
void add(int pos,int a)
{
    for(register int i=pos;i<=n;i+=lowbit(i))
    c[i]+=a;
}
int query(int pos)
{
    int summ=0;
    for(register int i=pos;i>0;i-=lowbit(i))
    summ+=c[i];
    return summ;
}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;i++)
    {
        cin>>a;
        add(i,a);
    }
    for(register int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        if(x==1)
            add(y,z);
        if(x==2)
            cout<<query(z)-query(y-1)<<endl;
    }
}