3198: 区间和线段树

jyssh / 2023-09-01 / 原文

描述

给定n个数据，有两个操作，加减其中的一个数据，当然还可查询在某段数据的和。

输入

输入数据有多组，每组数据的
第一行输入n，1=<n<=500000,代表数据的个数。
第二行输入具体数据，数据为正整数，范围在1到10000.
第三行输入m，1<=m<=100000,表示操作的次数。包含了修改和查询操作。
下面m行就是具体的操作了。
C i x 表示为第i个元素加上x，x范围在1到10000.
Q i j 表示查询区段i到j的和。保证输入的i<=j.
以EOF结束。

输出

输出查询后的区段和。

样例输入

8
1 5 9 11 2 8 15 6
4
Q 1 3
C 2 10
Q 1 4
Q 2 5

样例输出

15
36
37

泪目，终于会线段树了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10,inf = 0x3f3f3f3f;
int n,m;
int a[N],sum[N * 4];
void build(int l,int r,int rt)
{
    if(l == r)
    {
        sum[rt] = a[l];return;
    }
    int mid = (l + r) / 2;
    build(l,mid,rt * 2);
    build(mid + 1,r,rt * 2 + 1);
    sum[rt] = sum[rt*2] + sum[rt*2+1]; 
}
void change(int k,int l,int r,int p,int v) //单点修改 在p的位置加上v 
{
    if(r < p || l > p)return ;
    if(l == r && l == p)
    {
        sum[k] += v;
        return ;
    }
    int mid = (l + r) / 2;
    change(k * 2 , l , mid , p , v);
    change(k * 2 + 1 , mid + 1 , r , p , v);
    sum[k] = sum[k * 2] + sum[k * 2 + 1]; //更新信息 
} 
ll query(int k,int l,int r,int x,int y) //区间询问 询问x到y的区间和 
{
    if(y < l || x > r)return 0; //[x,y]不在[l,r]中 
    if(l >= x && r <= y)return sum[k];//[x,y]在[l,r]中 
    int mid = (l + r) / 2;
    ll res = 0;
    res += query(k * 2,l,mid,x,y);
    res += query(k * 2 + 1,mid + 1,r,x,y);
    return res;
} 
int main()
{
    while(cin >> n)
    {
        //memset(sum,0,sizeof(sum));
        for(int i = 1;i <= n; i++)
        {
            scanf("%d",&a[i]);
        }
        build(1,n,1);//构建线段树 
        cin >> m;
        char op;
        int l,r;
        while(m--)
        {    
            getchar();
            scanf("%c %d %d",&op,&l,&r);
            if(op=='C')change(1,1,n,l,r);
            else printf("%d\n",query(1,1,n,l,r));
        }
    }
     return 0;
}