动态求连续区间和


题目

给定 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
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例:
11
30
35

分析

图片来源于百度

线段树也可以解决单点修改,区间查询,结构体中可以是表示求和的sum,也可以是其他的,例如求最大值最小值,

代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int w[100006];
struct node{
    int l,r;
    int sum;
}aa[400006];

void pushup(int u)
{  //用子节点的信息去更新父节点
    aa[u].sum=aa[u*2].sum+aa[u*2+1].sum;
}

void build(int u,int l,int r) //根节点是u,在l-r之间建立线段树
{  //建立一个线段树
    if(l==r) aa[u]={l,r,w[l]};
    else
    {
        aa[u]={l,r};//首先对线段树进行初始化
        int mid=(l+r)/2;
        build(u*2,l,mid);build(u*2+1,mid+1,r);//左右递归建立线段树
        pushup(u);//建立之后用子节点的信息更新父节点
    }
}

int query(int u,int l,int r)  //根节点是u,目标区间为l到r
{  //询问操作
    if(l<=aa[u].l&&aa[u].r<=r) return aa[u].sum;//如果当前区间已包括目标区间,直接返回
    int mid=(aa[u].l+aa[u].r)/2;
    int sum=0;
    if(l<=mid) sum+=query(u*2,l,r);
    if(r>mid) sum+=query(u*2+1,l,r);//递归查询
    return sum;
}

void modify(int u,int x,int v) 
{  //更改操作,根节点是u,在位置x上加上v
    if(aa[u].l==aa[u].r) aa[u].sum+=v;
    else
    {
        int mid=(aa[u].l+aa[u].r)/2;
        if(x<=mid) modify(u*2,x,v);
        else modify(u*2+1,x,v);
        pushup(u);
    }
}

int main()
{
    cin>>n>>m;
    int x,a,b;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    while(m--)
    {
        cin>>x>>a>>b;
        if(!x) cout<<query(1,a,b)<<endl;
        else modify(1,a,b);
    }
    return 0;
}

Author: 眼里有星星
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source 眼里有星星 !
 Previous
差分 差分
一维差分题目输入一个长度为n的整数序列。接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数n和m。第二行包含n个整数,表示整数序列。
2020-02-23
Next 
数列区间最大值 数列区间最大值
题目输入一串数字,给你 M 个询问,每次询问就给你两个数字 X,Y,要求你说出 X 到 Y这段区间内的最大数。输入格式第一行两个整数 N,M表示数字的个数和要询问的次数;接下来一行为 N个数;接下来 M行,每行都有两个整数 X,Y。输出格式
2020-02-23
  TOC