A Segment Tree is a binary tree where each node stores an aggregate (sum, min, max) for a range of the original array. It supports range queries and point updates in O(log n) time. It is built in O(n) time and is essential for competitive programming and systems with frequent range operations.
vector<int> tree;
void build(vector<int>& arr, int node, int l, int r) {
if(l==r){tree[node]=arr[l];return;}
int m=(l+r)/2;
build(arr,2*node,l,m); build(arr,2*node+1,m+1,r);
tree[node]=tree[2*node]+tree[2*node+1];
}
int query(int node,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0;
if(ql<=l&&r<=qr)return tree[node];
int m=(l+r)/2;
return query(2*node,l,m,ql,qr)+query(2*node+1,m+1,r,ql,qr);
}
void update(int node,int l,int r,int idx,int val){
if(l==r){tree[node]=val;return;}
int m=(l+r)/2;
if(idx<=m)update(2*node,l,m,idx,val);
else update(2*node+1,m+1,r,idx,val);
tree[node]=tree[2*node]+tree[2*node+1];
}A segment tree over an n-element array has at most 4n nodes. Each leaf stores one array element. Each internal node stores the aggregate (e.g., sum) of the range it covers.
To query [ql, qr]: if the current node range is entirely outside [ql,qr] return 0; if entirely inside return node value; otherwise combine results from left and right children.
To update index i: traverse from root to the leaf, updating each ancestor on the way back up. This updates all O(log n) nodes that cover index i.
For range updates (add x to all elements in [l,r]), lazy propagation defers updates: store pending update at the node and propagate downward only when the child is actually visited.
Quiz coming soon for this algorithm.