树状数组是个好东东，我们一定要学会。
单点修改需，树状数组只需
。
区间查询需，树状数组只需
。
区间修改与查询，用它！用它！用它！！！
树状数组基本概念
树状数组的核心思想有关于二进制，不算特别难，而且代码贼短，适合作者这种小菜。
树状数组就是让需要改变的那个区间的第一个数加上改变的大小；让区间最后一个数的后一个数减去要改变的大小（类似差分）。第一个数加完后，使包含它的数也加上改变的大小；最后一个数的后一个数减完后，使包含它的数也减上改变的大小。
好，讲完这么多，你们肯定不理解，接下来我来解释（说了一堆废话）
树状数组单点修改
进入正题。
区间修改我们普通修改是不是需要，但是我们用树状数组只需要
，是不是很优呢？
当我们修改第一个数的时候，让他增加一个数n（我们假定n为2）。但在个时候，有一些本来包含这个数的大数就不服了：“我们包含他，他咋还比我们大了呢？”，所以说这个时候，为了平复民情啊，我们还需要把包含这个数的大数也加上2，附上一张图：
看，比如说我们要更改的是的话，那包含他的数是不是有：
。所以说我们需要让这些数也加上
。
这时候就会有同学问了：“怎么找到包含他的数呢？”
诶，问得好！
我也不知道。
啊开个玩笑，我怎么可能不知道呢？
前面我们说了树状数组的核心思想就是二进制，接下来，重要的角色登场了，他就是——。
lowbit
lowbit是树状数组必不可少的一部分。 ————作者
来，让我们一起找规律。
包含了
，那他们有什么规律呢？接下来请看：
的二进制是多少？对，是
；
的二进制是多少？对，是
；
的二进制是多少？对，是
；
的二进制是多少？对，是
。
你发现了什么规律？
对，每次二进制最低位上的都又加上了一个
：
最低位上的
加上了一个
，进位，变成了
；然后再次进位，变成了
，是不是这样？
来，让我们再找一组数据：
的二进制是
；
的二进制是
；
的二进制是
；
的二进制是多少？对，是
。
看，是不是也是这样？
好了，我们找到规律了，【庆祝】！！！
这时候有同学就会抽击我们幼小的心灵，讲这么多怎么实现呢？
说的依旧很好！！！
我依旧不知道......
啊我依旧开个玩笑，我依旧怎么可能不知道呢？
接下来把压力给到我们的主角——【欢呼】【欢呼】
代码很短，只有一行，但他却是树状数组中最不可缺少的一份！！！
他就是专门来解决这种问题的，具体实现就是：
int lowbit(int x){
return x & -x;
}这么短？
是的，就是这么短。
他就是让数字语上一个这个数字的负数，最后就是将最低位的加上
，非常难理解，大家记住就行，相信几行代码各位大佬肯定能记住，对吧？
说完了，树状数组单点修改的一个大问题也解决了，让我们继续学习单点修改。
树状数组单点修改
当我们解决了如何求出包含这个数字的大数时，单点修改我们也就快学完了。
接下来我们首先让要修改的数字增加改变的大小，再让序列中包含
的数字也加上改变的大小，也就是
。
举个栗子：
我们假定为
。
第一次：;
第二次：，让
;
第三次：，让
;
第四次：，让
；
第五次：，我们发现
大于序列长度，说明超出我们的序列了，结束。
好，模拟完了，大家是不是觉得思路更《清晰》了呢？
也就是循环，让序列的第项加上
，然后让
，终止条件是判断
是否大于序列总长度。
上代码！！！
int lowbit(int m){
return m&(-m);
}
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}好了，树状数组单点修改就告一段落，接下来有请的是——树状数组区间查询！！！
树状数组区间查询
想要学会树状数组区间查询，首先我们要先学会树状数组单点查询。
其实吧，树状数组单点查询和单点修改没有太多的不同，只不过一个是从到
（总共的数字），一个是从
（当前这个数字）到
，具体是怎么做到的，接下来就和我一起看看吧！！！
单点修改我们是让所有包含它的数字都加上要改变的大小，而单点查询就是寻找它包含的数总共的大小啦！是不是很相似呢？所以说我们直接——上代码！！！
int sum(int x){
int ans=0;
while(x!=0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}好了，这就是今天讲的内容了，你们学废了吗？（记得交学费！！！疯狂暗示）