Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
8
Indexable
#include <iostream>
#include <vector>

using namespace std;


#define vi vector<int>
#define pb push_back
#define ll long long
#define vl vector<ll>

const int S = 320;

int n, q;
vi a;
vl sum;

ll stup(int l, int r) {
    ll res = 0;
    for (int i = l; i <= r; i++) res += a[i];
    return res;
}

void update(int pos, int val) {
    sum[pos / S] += val - a[pos];
    a[pos] = val;
}

ll get(int l, int r) {
    int b1 = l / S;
    int b2 = r / S;
    if (b1 == b2) return stup(l, r);
    ll res = 0;
    res += stup(l, (b1 + 1) * S - 1);
    res += (b2 * S, r);
    for (int b = b1 + 1; b < b2; b++) res += sum[b];
    return res;
}

int main()
{
    freopen("sum.in", "r", stdin);
    freopen("sum.out", "w", stdout);
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    sum.resize(n);
    for (int i = 0; i < n; i++) sum[i] = 0;
    for (int i = 0; i < n; i++) sum[i / S] += a[i];
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, x;
            cin >> pos >> x;
            pos--;
            update(pos, x);
        }
        else {
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            cout << get(l, r) << endl;
        }
    }
    return 0;
}
Editor is loading...
Leave a Comment