区间和

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1154 字

n个元素初始全为0，m次操作：k=0把位置a

一本通
例

正文

/*
原题：一本通 4.3 例 1 区间和
题意：n 个元素初始全为 0，m 次操作：k=0 把位置 a 的数值加上 b；k=1 询问区间 [a,b] 的和。
思路：单点修改 + 区间求和，用线段树维护区间和即可；下标 1 基。
复杂度：时间 O((n+m) log n)，空间 O(n)。
易错点：初始全为 0，不要读入任何初始序列；位置与值用 long long 防溢出。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll sum[N*4];
void update(int node,int l,int r,int pos,ll v){
    if(l==r){
        sum[node]+=v;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid){
        update(node*2,l,mid,pos,v);
    }else{
        update(node*2+1,mid+1,r,pos,v);
    }
    sum[node]=sum[node*2]+sum[node*2+1];
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[node];
    }
    int mid=(l+r)/2;
    ll res=0;
    if(ql<=mid){
        res+=query(node*2,l,mid,ql,qr);
    }
    if(qr>mid){
        res+=query(node*2+1,mid+1,r,ql,qr);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int k,a,b;
        cin>>k>>a>>b;
        if(k==0){
            update(1,1,n,a,(ll)b);
        }else{
            cout<<query(1,1,n,a,b)<<"\n";
        }
    }
    return 0;
}

区间和

正文

一本通·提高篇的其它内容