分块思想解法

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ULL unsigned long long
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int id[N],a[N],b[N],len,s[N];
void modify(int x,int c)
{
    int tid = id[x];
    a[x] += c;
    s[tid] += c;
}
int query(int l,int r)
{
    int sid = id[l] , eid = id[r];
    int res = 0;
    if(sid == eid)
    {
        for(int i=l;i<=r;i++) res = (res + a[i] + b[sid]);
        return res;
    }

    for(int i=l;id[i]==sid;i++) res = (res + a[i] + b[sid]);
    for(int i=sid+1;i<eid;i++) res = (res + s[i]);
    for(int i=r;id[i]==eid;i--) res = (res + a[i] + b[eid]);
    return res;
}
void solve()
{
    cin >> n >> m;
    len = sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        id[i] = (i-1) / len + 1;
        s[id[i]] += a[i];
    }

    for(int i=1;i<=m;i++)
    {
        int op,a,b;
        cin >> op >> a >> b;
        if(op == 1) modify(a,b);
        else cout << query(a,b)<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.28 13:08:13
 */

参考答案：

#include<iostream>//树状数组解法
using namespace std;
const int N = 100010;
int a[N], c[N];
int n, m;
int lowbit(int x)
{
    return x & -x;
}
void add(int u, int v)
{
    for (int i = u; i <= 100001; i += lowbit(i)) c[i] += v;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) add(i, a[i]);
    for (int i = 1; i <= m; ++i)
    {
        int k, a, b;
        scanf("%d%d%d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(b) - query(a - 1));
        else add(a, b);
    }
    return 0;
}

#include<iostream>//线段树解法
using namespace std;
const int N = 100010;
struct node
{
    int l, r;
    int sum;
};
int a[N];
node tr[4 * N];
void push_up(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
    if (l == r) tr[u] = { l,r,a[r] };//
    else
    {
        tr[u] = { l,r };
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);//
        push_up(u);
    }
}
int query(int u, int l, int r)
{
    int res = 0;
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) res += query(u << 1, l, r);//当l <= mid时，r也可能比mid小，此时如果把r更新成mid，那就会错误地把要查询的区间变长。
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}
void modify(int u, int v, int x)
{
    if (tr[u].l == tr[u].r) tr[u].sum += x;
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (v <= mid) modify(u << 1, v, x);
        else modify(u << 1 | 1, v, x);
        push_up(u);
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (!a)
        {
            int t = query(1, b, c);
            printf("%d\n", t);
        }
        else modify(1, b, c);
    }
    return 0;
}