分块思想解法

#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
 */