What is a Segment Tree?
A segment tree is a binary tree that efficiently handles range queries and point updates. Built on an array of size n, it answers range queries in O(log n) time.
Building the Tree
``cpp
int tree[4 * MAXN];
void build(int node, int start, int end, int arr[]) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(2*node, start, mid, arr);
build(2*node+1, mid+1, end, arr);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
`
Range Sum Query
`cpp
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2*node, start, mid, l, r)
+ query(2*node+1, mid+1, end, l, r);
}
``
Applications
Segment trees are foundational. Learn them well.