Untitled

 avatar
unknown
plain_text
2 years ago
1.9 kB
3
Indexable
#include <iostream>

using namespace std;

const int N = 300010;

int tsum[4 * N], tadd[4 * N], a[N];
int n, q;

void merge(int v) {
    tsum[v] = tsum[v * 2] + tsum[v * 2 + 1];
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tsum[v] = a[tl];
        tadd[v] = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    merge(v);
}

void upd(int v, int val, int tl, int tr) {
    tadd[v] += val;
    tsum[v] += (tr - tl + 1) * val;
}

void push(int v, int tl, int tr) {
    int tm = (tl + tr) / 2;
    if (tadd[v] != 0) {
        /*tadd[v * 2] += tadd[v];
        tsum[v * 2] += (tm - tl + 1) * tadd[v];
        tadd[v * 2 + 1] += tadd[v];
        tsum[v * 2 + 1] += (tr - tm) * tadd[v];*/
        upd(v * 2, tadd[v], tl, tm);
        upd(v * 2 + 1, tadd[v], tm + 1, tr);
        tadd[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (l == tl && r == tr) {
        tsum[v] += (tr - tl + 1) * val;
        tadd[v] += val;
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), val);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
    merge(v);
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return tsum[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            int val;
            cin >> val;
            update(1, 1, n, l, r, val);
        }
        else cout << sum(1, 1, n, l, r) << "\n";
    }
    return 0;
}
Editor is loading...