线段树解决单点修改和区间查询问题(动态求连续区间和)

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

 

上一篇:「USACO11DEC」Grass Planting G 题解 (树链剖分)


下一篇:xctf攻防世界 CRYPTO高手进阶区 banana-princess