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; }