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

本文主要是介绍线段树解决单点修改和区间查询问题（动态求连续区间和），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

这篇关于线段树解决单点修改和区间查询问题（动态求连续区间和）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！