세그먼트 트리 기초: 백준 2042 구간 합 구하기 [C/C++]

 

#include <iostream>
#include <cmath>
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
#define long long ll
using namespace std;
ll n, m, k, from;
ll arr[11111111];
void update(ll location, ll v) {
    ll idx = location + from - 1;
    arr[idx] = v;
    for (ll i = idx / 2; i >= 1; i /= 2) {
        arr[i] = arr[i * 2] + arr[i * 2 + 1];
    }
}
ll sum(ll l, ll r, ll idx = 1, ll L = 1, ll R = from) {
    if (l > R or r < L) return 0;
    else if (l <= L and r >= R) return arr[idx];
    ll m = (L + R) / 2;
    return sum(l, r, idx * 2, L, m) + sum(l, r, idx * 2 + 1, m + 1, R);
}
 
int main() {
    fastio();
    cin >> n >> m >> k;
    from = ((n & (n - 1)) == 0) ? pow(2, (int)log2(n)) : pow(2, (int)log2(n) + 1);
 
    for (ll i = from; i < from + n; i++) 
        cin >> arr[i];
 
    for (ll i = from - 1; i >= 1; --i) 
        arr[i] = arr[i * 2] + arr[i * 2 + 1];
 
    for (ll i = 0; i < m + k; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            update(b, c);
        }
        else {
            cout << sum(b, c) << "\n";
        }
    }
}