1264. 动态求连续区间和
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。
输入格式
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n 个整数，表示完整数列。
接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1 开始计数。
输出格式
输出若干行数字，表示 k=0 时，对应的子数列 [a,b]的连续和。
数据范围
1≤n≤100000
1≤m≤100000
1≤a≤b≤n
数据保证在任何时候，数列中所有元素之和均在 int 范围内。
线段树的存储结构：
线段树是用数组来模拟树形结构，对于每一个节点R ,左子节点为 2*R (一般写作R<<1)右子节点为 2*R+1（一般写作R<<1|1）
然后以1为根节点，所以，整体的统计信息是存在节点1中的。
这么表示的原因看下图就很明白了，左子树的节点标号都是根节点的两倍，右子树的节点标号都是左子树+1：
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int w[N];
struct node{
int l,r;//左右区间
int sum;//总和
}tr[4*N];//记得开4倍空间
void push_up(int u){
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//当前节点的和等于它的两个子节点的和
}
void build(int u,int l,int r){//参数：当前节点编号、左边界、右边界
if(l==r) tr[u]={l,r,w[r]};//如果已经是叶节点，就直接赋值，也是递归的终止条件
else{
tr[u]={l,r};//先初始化一下左右区间
int mid=l+r>>1;
build(u<<1,l,mid);//先递归一下左子节点
build(u<<1|1,mid+1,r);//再递归一下右子节点
push_up(u);//更新当前节点信息
}
}
int query(int u,int l,int r){//查询的过程是从根节点开始往下找对应的一个区间
//如果当前区间已经被要查询的区间完全包含了，则直接返回当前区间的和
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;//也是递归的终止条件
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid) res+=query(u<<1,l,r);//l和r不变，还是用要查询的区间看当前区间是否被完全包含
if(r>=mid+1) res+=query(u<<1|1,l,r);//看一下当前区间的中点和右边界有没有交集
return res;
}
void modify(int u,int x,int v){//参数：节点编号、要修改的数的位置、要修改的值
if(tr[u].l==tr[u].r) tr[u].sum+=v;//如果已经是叶节点，则直接让总和加v
else{
int mid=tr[u].l+tr[u].r>>1;
//看一下x在左边的子节点还是在右边
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
push_up(u);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
build(1,1,n);/*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */
while(m--){
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(k==0) printf("%d\n",query(1,a,b));//查询的时候是从根节点往下查，所以当前节点编号传1
else modify(1,a,b);//也是先从根节点开始，直到叶节点再修改
}
return 0;
}