Segment Tree Basic

Node Divide With Segment Tree

Node Numbering (Segment Tree)

// build (node, begin, end)
build (1, 1, N)
{
    L = 2xN, R = (2xN) + 1 // Node Number Calculate
    mid = (begin + end) / 2
    left = (L, begin, mid)
    left = (R, mid+1, end)
}

Summation (Array)(Segment Tree)

Update Element (Segment Tree)

Query solve (Summation)

• inner (when found the Node then return it)

• outer (when Not found the Node)

• Intersect --> between two ways (left or right)

code

#include "bits/stdc++.h"
#define ll long long 
using namespace std;
const ll N = 1e5+5;

const int maxN = 1e5 + 9;
long long a[maxN], t[4 * maxN];

//BUILD
void build(int n, int b, int e) {
    if (b == e) {
        t[n] = a[b];
        return;
    }
    int mid = (b + e) / 2, l = 2 * n, r = (2 * n) + 1;
    build(l, b, mid);
    build(r, mid + 1, e);
    t[n] = t[l] + t[r];
}

//UPDATE
void update(int n, int b, int e, int i, int v) {
    if (i<b || i>e) {
        return;
    }
    if (b == e) {
        t[n] = v;
        return;
    }
    int mid = (b + e) / 2, l = 2 * n, r = (2 * n) + 1;
    update(l, b, mid, i, v);
    update(r, mid + 1, e, i, v);
    t[n] = t[l] + t[r];
}

// QUERY
long long query(int n, int b, int e, int i, int j) {
    if (e < i || j < b) {
        return 0;
    }
    if (b >= i && e <= j) {
        return t[n];
    }
    int mid = (b + e) / 2, l = 2 * n, r = (2 * n) + 1;
    return query(l, b, mid, i, j) + query(r, mid + 1, e, i, j);
}

// MAIN FUNCTION
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }

    build(1, 1, n);
    while (m--) {
        int t;
        cin >> t;
        if (t == 1) {
            int idx, v;
            cin >> idx >> v;
            idx++;
            update(1, 1, n, idx, v);
        }
        else {
            int l, r;
            cin >> l >> r;
            l++;
            long long ans = query(1, 1, n, l, r);
            cout << ans << '\n';
        }
    }
    return 0;
}