普通树状数组：

复杂度为 O(n\log n+q\log n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a, seed, m, t[10000010];
ll lowbit(ll x) { return x & -x; }
ll query(ll x)
{
    ll r = 0;
    for (ll i = x; i; i -= lowbit(i))
    {
        r += t[i];
    }
    return r;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &seed);
    mt19937 mt(seed);
    uniform_int_distribution<int> dist(0, 1e9);
    uniform_int_distribution<int> dist_cmd(1, 2);
    uniform_int_distribution<int> dist_x(1, n);
    for (ll i = 1; i <= n; ++i)
    {
        ll v = dist(mt);
        for (ll j = i; j <= n; j += lowbit(j))
        {
            t[j] += v;
        }
    }
    while (m--)
    {
        ll cmd = dist_cmd(mt);
        if (cmd == 1)
        {
            ll x = dist_x(mt), v = dist(mt);
            for (ll i = x; i <= n; i += lowbit(i))
            {
                t[i] += v;
            }
        }
        else
        {
            ll x = dist_x(mt), y = dist_x(mt);
            if (x > y)
            {
                swap(x, y);
            }
            printf("%lld\n", query(y) - query(x - 1));
        }
    }
    return 0;
}

快速树状数组：

复杂度为 O(n+q\log n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a, seed, m, t[10000010];
ll lowbit(ll x) { return x & -x; }
ll query(ll x)
{
    ll r = 0;
    for (ll i = x; i ; i -= lowbit(i))
    {
        r += t[i];
    }
    return r;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &seed);
    mt19937 mt(seed);
    uniform_int_distribution<int> dist(0, 1e9);
    uniform_int_distribution<int> dist_cmd(1, 2);
    uniform_int_distribution<int> dist_x(1, n);
    for (ll i = 1; i <= n; ++i)
    {
        t[i] += dist(mt);
        ll j = i + lowbit(i);
        if (j <= n)
        {
            t[j] += t[i];
        }
    }
    while (m--)
    {
        ll cmd = dist_cmd(mt);
        if (cmd == 1)
        {
            ll x = dist_x(mt), v = dist(mt);
            for (ll i = x; i <= n; i += lowbit(i))
            {
                t[i] += v;
            }
        }
        else
        {
            ll x = dist_x(mt), y = dist_x(mt);
            if (x > y)
            {
                swap(x, y);
            }
            printf("%lld\n", query(y) - query(x - 1));
        }
    }
    return 0;
}