Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

#define Achilles ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
#define M 1000000007
#define pp push_back
const int N = (1 << 18);

struct Node {
    ll sum;

    Node() {
        sum = 0;
    }
};

int a[N], n, q;
Node seg[N];

ll merge(Node &l, Node &r) {
    return l.sum + r.sum;
}

void build(int ns = 0, int ne = n - 1, int ni = 0) {
    if (ns == ne) {
        seg[ni].sum = a[ns];
        return;
    }
    int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2;
    build(ns, m, l);
    build(m + 1, ne, r);
    seg[ni].sum = merge(seg[l], seg[r]);
}

ll query(int qs, int qe, int ns = 0, int ne = n - 1, int ni = 0) {
    if (qe < ns || ne < qs || seg[ni].sum == 0) return 0;
    if (qs <= ns && ne <= qe) return seg[ni].sum;

    int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2;
    ll ans_l = query(qs, qe, ns, m, l);
    ll ans_r = query(qs, qe, m + 1, ne, r);

    return (ans_l + ans_r);
}

void update(int idx, ll val, int ns = 0, int ne = n - 1, int ni = 0) {
    if (idx < ns || ne < idx) return;
    if (ns == ne) {
        seg[ni].sum = val;
        return;
    }
    int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2;
    update(idx, val, ns, m, l);
    update(idx, val, m + 1, ne, r);
    seg[ni].sum = merge(seg[l], seg[r]);
}

void func() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build();
    int t;
    while (q--) {
        cin >> t;
        if (t == 1) {
            int idx, val;
            cin >> idx >> val;
            update(idx, val);
        } else {
            int l, r;
            cin >> l >> r;
            r--;
            cout << query(l, r) << '\n';
        }
    }
}

int main() {
    Achilles
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t = 1;
//    cin >> t;
    while (t--) {
        func();
    }
}
Leave a Comment