세그트리

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

ll update

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

ll n, m, k;

vector<ll> a, segTree;

ll init(ll i, ll s, ll e) {

    if (s == e) return segTree[i] = a[s];

    ll mid = (s + e) >> 1;

    return segTree[i] = init(2 * i, s, mid) + init(2 * i + 1, mid + 1, e);

}

ll update(ll i, ll s, ll e, ll idx, ll value) {

    if (e < idx || idx < s) return segTree[i];

    if (s == e) return segTree[i] = value;

    ll mid = (s + e) >> 1;

    return segTree[i] = update(2 * i, s, mid, idx, value) +

                        update(2 * i + 1, mid + 1, e, idx, value);

}

ll query(ll i, ll s, ll e, ll l, ll r) {

    if (e < l || r < s) return 0;

    if (l <= s && e <= r) return segTree[i];

    ll mid = (s + e) >> 1;

    return query(2 * i, s, mid, l, r) + query(2 * i + 1, mid + 1, e, l, r);

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> k;

    a.resize(n + 1);

    segTree.resize(4 * n);

    int i;

    for (i = 1; i <= n; i++) cin >> a[i];

    init(1, 1, n);

    for (i = 1; i <= m + k; i++) {

        ll op;

        cin >> op;

        if (op == 1) {

            ll idx, val;

            cin >> idx >> val;

            update(1, 1, n, idx, val);

            a[idx] = val;

        } else if (op == 2) {

            ll S, E;

            cin >> S >> E;

            cout << query(1, 1, n, S, E) << '\n';

        }

    }

    return 0;

}

---

 

 

void update

---

 

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

ll n, m, k;

vector<ll> a, segTree;

ll init(ll i, ll s, ll e) {

    if (s == e) return segTree[i] = a[s];

    ll mid = (s + e) / 2;

    return segTree[i] = init(2 * i, s, mid) + init(2 * i + 1, mid + 1, e);

}

void update(ll i, ll s, ll e, ll idx, ll diff) {

    if (e < idx || idx < s) return;

    segTree[i] += diff;

    if (s != e) {

        ll mid = (s + e) / 2;

        update(2 * i, s, mid, idx, diff);

        update(2 * i + 1, mid + 1, e, idx, diff);

    }

}

ll query(ll i, ll s, ll e, ll l, ll r) {

    if (e < l || r < s) return 0;

    if (l <= s && e <= r) return segTree[i];

    ll mid = (s + e) / 2;

    return query(2 * i, s, mid, l, r) + query(2 * i + 1, mid + 1, e, l, r);

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> k;

    a.resize(n + 1);

    segTree.resize(4 * n);

    int i;

    for (i = 1; i <= n; i++) cin >> a[i];

    init(1, 1, n);

    for (i = 1; i <= m + k; i++) {

        ll op;

        cin >> op;

        if (op == 1) {

            ll idx, val;

            cin >> idx >> val;

            update(1, 1, n, idx, val - a[idx]);

            a[idx] = val;

        } else if (op == 2) {

            ll S, E;

            cin >> S >> E;

            cout << query(1, 1, n, S, E) << '\n';

        }

    }

    return 0;

}

---