segment tree implementation in c++

segment_tree.cpp

#include <bits/stdc++.h>

using namespace std;

int func(int a, int b) {
    // binary function
    // ex) return gcd(a, b);
    // ex) return a * b;
    // ex) return a ^ b;
    // BUT! associated law has to be held
    return a + b;
}

vector<int> seg;

void init(vector<int> &vec, int node, int left, int right) {
    if(left == right) {
        seg[node] = vec[left - 1];
        return;
    }
    init(vec, node << 1, left, (left + right) >> 1);
    init(vec, node << 1 | 1, ((left + right) >> 1) + 1, right);
    seg[node] = func(seg[node << 1], seg[node << 1 | 1]);
}

void update(int node, int left, int right, int index, int value) {
    if(index < left || right < index) return;
    if(left == right) {
        seg[node] = value;
        return;
    }
    update(node << 1, left, (left + right) >> 1, index, value);
    update(node << 1 | 1, ((left + right) >> 1) + 1, right, index, value);
    seg[node] = func(seg[node << 1], seg[node << 1 | 1]);
}

int query(int node, int left, int right, int start, int end) {
    if(start <= left && right <= end) return seg[node];
    int mid = (left + right) >> 1;
    if(mid < start) return query(node << 1 | 1, mid + 1, right, start, end);
    if(mid + 1 > end) return query(node << 1, left, mid, start, end);
    return func(query(node << 1, left, mid, start, end), query(node << 1 | 1, mid + 1, right, start, end));
}

int main() {
    int size = 4;
    seg.resize(4 * size);
    vector<int> vec{1, 2, 3, 4};
    init(vec, 1, 1, size);
    update(1, 1, size, 2, 4);
    cout << query(1, 1, size, 2, 4) << endl;
}