数列操作

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

树状数组点改区间和

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1535
// 题意：n 个数，两种操作：k=0 求子数列 [a,b] 连续和；k=1 第 a 个数加 b。n,m 各最多 1e5。
// 思路：树状数组单点加、区间求和。下标从 1 开始，查询 [a,b] 即前缀和 b 减前缀和 a-1。
// 复杂度：O((n+m) log n) 时间 / O(n) 空间
// 易错点：a,b 是 1 基下标；k=1 是加值不是赋值；多组输出按查询顺序。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long bit[MAXN];
int n;
void add(int i, long long v){
    for(;i<=n;i+=i&-i) bit[i]+=v;
}
long long sum(int i){
    long long s=0;
    for(;i>0;i-=i&-i) s+=bit[i];
    return s;
}
int main(){
    int m;
    if(!(cin>>n>>m)) return 0;
    for(int i=1;i<=n;i++){
        long long x; cin>>x;
        add(i,x);
    }
    while(m--){
        int k,a,b;
        cin>>k>>a>>b;
        if(k==0) cout<<sum(b)-sum(a-1)<<"\n";
        else add(a,b);
    }
    return 0;
}

数列操作

正文

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