超级常用的小工具:)
简介
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，能快速查询特定区间的和；主要操作分为建树、修改、查询。
建树
一种类似DFS的方法构建一棵二叉树，从上到下、从左到右标记树的节点,一号节点是[1,n]，二号节点就是[1,n/2],三号节点为[n/2+1,n];以此类推
某渣渣自画:)
核心代码：
void build_tree(int now, int l, int r){
if(l==r){
scanf("%d", &tp[now]);
return;
}
int mid=(l+r)/2;
build_tree(now*2, l, mid);
build_tree(now*2+1, mid+1, r);
tp[now]=tp[now*2]+tp[now*2+1];
}
修改
重新更新了一次节点，每个涉及到的节点都会被更新，从而形成新的线段树(二叉树);相当于构建树的简化版?(其实都一样)
核心代码：
void update(int now, int l, int r){
if(l==r && l==pos){
tp[now]=val;
return;
}
int mid=(l+r)/2;
if(mid>=pos)
update(now*2, l, mid);
else
update(now*2+1, mid+1, r);
tp[now]=tp[now*2]+tp[now*2+1];
}
查询
我们已经得到了一个区间简化的树，那么问题来了，总不可能不求区间值吧？
我们的树构建的时候用的是二分的思想，很多时候需要几个节点相加，还记得节点代表的是哪段区间吗？
不记得也没关系，你只需要知道当你现在的区间的l大于等于所求的L，左边包含一部分数据是你需要的；当你现在的区间的r小于所求的R的时候，右边数据必定是有你需要的；（>=?）
核心代码：
int query(int now, int l, int r){
if(L<=l && r<=R)
return tp[now];
int sum=0;
int mid=(l+r)/2;
if(L<=mid)
sum+=query(now*2, l, mid);
if(R>mid)
sum+=query(now*2+1, mid+1, r);
return sum;
}
有没有感觉上述代码非常像？
是的，他就是非常像，理解第一个之后剩下的势如破竹，
相应的变形代码也很容易构建(比如[l,r]加减x)，
线段树的应用绝对不止这一点，有心的大佬多刷刷题就会理解里面的奥妙了
