AcWing_1264 动态求连续区间和(树状数组/线段树)

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100010;
int a[N], tr[N];
int lowbit(int x){return x & -x;}
void add(int u, int v){
    for(int i = u; i <= n; i += lowbit(i)) tr[i] += v;
}
int search(int l, int r){
    int suml = 0, sumr = 0;
    for(int i = l - 1; i >= 1; i -= lowbit(i)) suml += tr[i];
    for(int i = r; i >= 1; i -= lowbit(i)) sumr += tr[i];
    return sumr - suml;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) add(i, a[i]);
    while(m --){
        int k, a, b;
        cin >> k >> a >> b;
        if(!k) cout << search(a, b) << "\n";
        else add(a, b);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100010;
int arr[N], sum[4 * N], tag[4 * N];
void push(int u){
    sum[u] = sum[2 * u] + sum[2 * u + 1];
}
void down(int l, int r, int u){
    if(tag[u]){
        int mid = l + r >> 1;
        sum[2 * u] += (mid - l + 1) * tag[u];
        tag[2 * u] += tag[u];
        sum[2 * u + 1] += (r - mid) * tag[u];
        tag[2 * u + 1] += tag[u];
        tag[u] = 0;
    }
}
void build(int l, int r, int u){
    if(l == r){
        sum[u] = arr[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, 2 * u);
    build(mid + 1, r, 2 * u + 1);
    push(u);
}
void update(int a, int l, int r, int u, int v){
    if(l == r){
        arr[l] += v;
        sum[u] += v;
        return;
    }
    int mid = l + r >> 1;
    if(a <= mid) update(a, l, mid, 2 * u, v);
    else update(a, mid + 1, r, 2 * u + 1, v);
    push(u);
}
int query(int L, int R, int l, int r, int u){
    if(L <= l && r <= R) return sum[u];
    int res = 0;
    down(l, r, u);
    int mid = l + r >> 1;
    if(L <= mid) res += query(L, R, l, mid, 2 * u);
    if(R > mid) res += query(L, R, mid + 1, r, 2 * u + 1);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    build(1, n, 1); // a[1~n]，线段树根节点从1开始
    while(m --){
        int k, a, b;
        cin >> k >> a >> b;
        if(k) update(a, 1, n, 1, b);  // a[1~n]范围，根节点为1，将a节点+b
        else cout << query(a, b, 1, n, 1) << "\n";  // a[1~n]范围，根节点为1，查找区间为[a, b]
    }
    return 0;
}