学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是 ））。写完这篇总结后我会挑一些比较好的题再写一篇博客，算是题解总结吧。
建树、修改和查询
题目一：P3372 【模板】线段树 1
我们从模板题入手，题目中的两个操作正是线段树很经典的操作：区间修改和区间查询。我们思考以下几种做法：
① 如果让我们暴力地修改区间每一个值，再暴力查询区间的每一个值，修改和暴力都是 。其实它和树关系不太大，实际操作时有类似在树上节点的跳跃的过程，但是在写代码的时候它也不过是个一维数组而已，和线段树还是有一点点像的，不过是将线段树的一些精华部分充分压缩了。来，让我们看看传说中的树状数组长啥样（纯手工，不要在意细节）：
绿油油的就是树状数组啦，它头上红色的是这个下标对应的二进制,最底下的就是原数组了。直觉告诉你，他们之间隐约存在某些关系。你可能会觉得这里一共有两个数组，还有一堆连线，要维护起来是不是很麻烦啊。其实他们可以只用一个一维数组存储所有信息，而其中关键的纽带就是二进制。
我们设原数组为 \(A\) ,树状数组为 \(T\) ,定义连线的意义就是一个节点能管辖的范围。例如 \(T_1\) 能直接管辖管辖到 \(A_1\) , \(T_2\) 能管辖到 \(T_1\) （间接管辖到 \(A_1\)）和 \(A_2\), \(T_4\) 能管辖到 \(T_2\) 、\(T_3\) 和 \(A_4\) ,亦即 \(T_4\) 能管辖到原数组 \(A_1\) 、\(A_2\) 、\(A_3\)和 \(A_4\) ...以此类推，\(T_8\) 能管辖到原数组所有值。所以，我们只要存储 \(T_1\) , \(T_2\) 的值，原数组中 \(A_2\) 可以由这两者相减得到；同理， \(A_5\) 、\(A_6\) 、\(A_7\)和 \(A_8\) 的总和可以由 \(T_8\) 减去 \(T_4\) 得到。所以，我们只要保留树状数组，原数组的信息完全可以由树状数组维护出来，并且轻松知道任意一个区间的信息和。
那么新的问题出现了，我们如何知道谁管辖谁，他们之间有什么联系吗？这时，奇妙的二进制出现了。观察树状数组头上的二进制，看出被管辖者与管辖着之间在二进制上的联系了吗？揭晓答案，被管辖者加上 \(2^k\)，\(k\) 为被管辖者二进制末尾零的个数，即可得到管辖着的二进制！举个栗子，\(T_2\) 的二进制为 \(0010\) ,加上 \(2^1（0010）\) ,得到 \(0100\) ,即 \(T_4\) 。我们一般将 \(2^k\) 写成一个函数叫 \(lowbit\) ，树状数组下标 \(x\) 与它的 \(lowbit\) 如下关系：
证明其实没必要，会用就行，这涉及到负数在计算机中存储的形式，可以自己证一下。
修改update
P3374 【模板】树状数组 1
树状数组完全不用像线段树一样需要一个函数来建树，声明了一个一维数组（数组大小等于数据量即可，不用开多几倍）直接就可以进行修改查询等操作了。它的修改函数代码非常短，而且形式几乎不变。
void update(int now,int value){
while(now <= n){
t[now] += value;
now += lowbit(now);
}
}
三行循环就结束了，线段树自愧不如。这个函数的意义是在原数组的 \(now\) 的下标位置加上 \(value\) ,循环的终点是大于了树状数组的下标范围 \(n\) 。它是怎么通过加上 \(lowbit\) 实现的呢？来看下面这张图：
假如我们要修改原数组 \(5\) 这个位置的值，能管辖到它的只有 \(T_6\) 和 \(T_8\) 。因为我们要求区间和，所以 \(T_6\) 和 \(T_8\) 要都加上 \(T_5\) 修改后的值才行。这时我们用一个 \(lowbit\) 在循环中从 \(T_5\) 跳到 \(T_6\)，再跳到 \(T_8\) ，一气呵成。这样，单点修改操作就完成啦。
查询query
查询操作永远是和修改操作配套的，一切修改的目的都是为了查询的方便。既然修改代码这么短小精悍，那么查询代码就更加小巧了，请看：
ll query(int now){
ll ans = 0; //long long 类型的答案
while(now){
ans += t[now];
now -= lowbit(now);
}return ans;
}
代码的意义是查询原数组从 \(1\) 到 \(now\) 的前缀和，即从 \(A_1\) 到 \(A_{now}\) 的和。注意这时我们的 \(lowbit\) 操作变成了减，而之前修改操作是加。原理也可以看图说明：
图中我们查询的是 \(1\) ~ \(7\) 的前缀和，我们先加上 \(T_7\) 的答案，再减去它的 \(lowbit\) 跳到 \(T_6\) ，最后跳到 \(T_4\) ,因为 \(T_6\) 和 \(T_4\) 在前面的修改操作中已经维护出了自己管辖区域的区间和，都加上就是 \(1\) ~ \(7\) 的前缀和了。
知道了前缀和，区间和其实就很容易了，假如我们要求 \([x,y]\) 的区间和，其实就是 \(query(y)-query(x-1)\) ，注意是 \(x-1\) ，要自己想一想，这个地方总是容易被忽略。
完整代码
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define lowbit(x) x&(-x)
typedef long long ll;
const int maxn = 5e5+5;
int t[maxn],n,m,num;
void update(int now,int value){
while(now<=n){
t[now]+=value;
now += lowbit(now);
}
}
ll query(int now){
ll ans = 0; //long long 类型的答案
while(now){
ans += t[now];
now -= lowbit(now);
}return ans;
}
int main(){
speedUp_cin_cout
cin>>n>>m;
For(i,1,n) {
cin>>num;
update(i,num);
}int op,x,y;
For(i,1,m){
cin>>op>>x>>y;
if(op == 1) update(x,y);
else cout<<query(y)-query(x-1)<<endl;
}
return 0;
}
是不是比线段树短多了。这是单点修改，区间查询。洛谷还有道P3368 【模板】树状数组 2，是区间修改，单点查询。这就需要差分的思想了。所谓的差分，其实就是后一项与前一项的差，对于第一项而言，\(a[0] = 0\) 。设数组 \(a[~]=\{1,9,3,5,2\}\) ，那么差分数组\(t[~]=\{1,8,-6,2,-3\}\) ，即 \(t[i]=a[i]-a[i-1]\) ,那么 $$a[i]=t[1]+...+t[i]$$
这不就是前缀和吗?对原数组的区间修改，单点查询就是在其差分数组上单点修改，区间查询。但是要注意的是，这里的单点其实是要修改两个点。例如我们如果要让 \([2,3]\) 区间加上 \(4\) ,首先是要修改差分数组上的 \(t[2] +4\)， 然后还要修改 \(t[4]-4\) ,这也是很好理解的，毕竟 \([2,3]\) 区间比其他区间突出了一块，整体提高了 \(4\) ，而其他的区间的差分关系并没有被改变。这样，我们也可以很愉快地 \(AC\) 这道题了。
还有一些话
做模板题是快乐的（除了P6242 【模板】线段树 3）,但是实际应用起来是比较头疼的。因为线段树和树状数组灵活性很高，可以解决很多看似无法下手的问题，但是要维护的信息多得容易摸不着头脑（不知道为什么这样做就可以了），逻辑关系环环相扣，时不时就得感叹一下“妙”。这些都得做更多的题来体会了。还有不要死记模板，要清楚知道每一步的作用，很多时候一些顺序会颠倒，来解决不同的问题，这是需要警惕的。
如果觉得对你理解有帮助的希望给我点个赞哦，ο(=•ω＜=)ρ⌒☆