A segment tree splits the array into halves recursively. Every node stores the aggregate of its range; the root stores the whole array.
Why it matters:
Prefix sums answer range sums in O(1) but an update costs O(n). A segment tree makes both query and update O(log n).
Core Template (Sum)
class SegmentTree {
int n;
int[] tree;
public SegmentTree(int[] arr) {
n = arr.length;
tree = new int[4 * n];
build(arr, 1, 0, n - 1);
}
private void build(int[] arr, int node, int lo, int hi) {
if (lo == hi) { tree[node] = arr[lo]; return; }
int mid = (lo + hi) / 2;
build(arr, node * 2, lo, mid);
build(arr, node * 2 + 1, mid + 1, hi);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
public void update(int i, int val) {
update(1, 0, n - 1, i, val);
}
private void update(int node, int lo, int hi, int i, int val) {
if (lo == hi) { tree[node] = val; return; }
int mid = (lo + hi) / 2;
if (i <= mid) update(node * 2, lo, mid, i, val);
else update(node * 2 + 1, mid + 1, hi, i, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
public int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
private int query(int node, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0; // disjoint
if (l <= lo && hi <= r) return tree[node]; // covered
int mid = (lo + hi) / 2;
return query(node * 2, lo, mid, l, r)
+ query(node * 2 + 1, mid + 1, hi, l, r);
}
}class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr, node, lo, hi):
if lo == hi:
self.tree[node] = arr[lo]
return
mid = (lo + hi) // 2
self._build(arr, node * 2, lo, mid)
self._build(arr, node * 2 + 1, mid + 1, hi)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def update(self, i, val):
self._update(1, 0, self.n - 1, i, val)
def _update(self, node, lo, hi, i, val):
if lo == hi:
self.tree[node] = val
return
mid = (lo + hi) // 2
if i <= mid:
self._update(node * 2, lo, mid, i, val)
else:
self._update(node * 2 + 1, mid + 1, hi, i, val)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def query(self, l, r):
return self._query(1, 0, self.n - 1, l, r)
def _query(self, node, lo, hi, l, r):
if r < lo or hi < l:
return 0 # disjoint
if l <= lo and hi <= r:
return self.tree[node] # covered
mid = (lo + hi) // 2
return (self._query(node * 2, lo, mid, l, r)
+ self._query(node * 2 + 1, mid + 1, hi, l, r))class SegmentTree {
int n;
vector<int> tree;
void build(vector<int>& arr, int node, int lo, int hi) {
if (lo == hi) { tree[node] = arr[lo]; return; }
int mid = (lo + hi) / 2;
build(arr, node * 2, lo, mid);
build(arr, node * 2 + 1, mid + 1, hi);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int node, int lo, int hi, int l, int r) const {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return tree[node];
int mid = (lo + hi) / 2;
return query(node * 2, lo, mid, l, r) +
query(node * 2 + 1, mid + 1, hi, l, r);
}
public:
SegmentTree(vector<int>& arr)
: n(arr.size()), tree(4 * arr.size()) {
build(arr, 1, 0, n - 1);
}
void set(int i, int val) { setRec(1, 0, n - 1, i, val); }
void setRec(int node, int lo, int hi, int i, int val) {
if (lo == hi) { tree[node] = val; return; }
int mid = (lo + hi) / 2;
if (i <= mid) setRec(node * 2, lo, mid, i, val);
else setRec(node * 2 + 1, mid + 1, hi, i, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
long long sum(int l, int r) const {
return query(1, 0, n - 1, l, r);
}
};class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = Array(4 * this.n).fill(0);
this.#build(arr, 1, 0, this.n - 1);
}
#build(arr, node, lo, hi) {
if (lo === hi) {
this.tree[node] = arr[lo];
return;
}
const mid = (lo + hi) >> 1;
this.#build(arr, node * 2, lo, mid);
this.#build(arr, node * 2 + 1, mid + 1, hi);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
set(i, val) {
this.#set(this.#root(), 0, this.n - 1, i, val);
}
#set(node, lo, hi, i, val) {
if (lo === hi) {
this.tree[node] = val;
return;
}
const mid = (lo + hi) >> 1;
if (i <= mid) this.#set(node * 2, lo, mid, i, val);
else this.#set(node * 2 + 1, mid + 1, hi, i, val);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
sum(l, r) {
return this.#query(this.#root(), 0, this.n - 1, l, r);
}
#query(node, lo, hi, l, r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return this.tree[node];
const mid = (lo + hi) >> 1;
return (
this.#query(node * 2, lo, mid, l, r) +
this.#query(node * 2 + 1, mid + 1, hi, l, r)
);
}
#root() {
return 1;
}
}Everything else is this template with a different combiner.
Variant: Min Instead of Sum
Watch sum([1..2]) on [5, 2, 6, 1] — the query only visits nodes it can’t skip. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Segment Tree Range Sum Query
Answer range-sum queries over a prebuilt segment tree in O(log n).
Each node stores the sum of its range. A query walks the tree: disjoint nodes contribute 0, fully-covered nodes return their stored sum, and partially-overlapping nodes split into children. Only O(log n) nodes are visited per query.
1
tree built from arr = [5, 2, 6, 1]; each node stores its range sum
2
query(node, lo, hi):
3
if [lo,hi] disjoint from [l,r] → return 0
4
if [lo,hi] fully inside [l,r] → return node.sum
5
else split into children and add their answers
Change exactly two things — the combiner and the identity:
// disjoint → identity
if (r < lo || hi < l) return Integer.MAX_VALUE;
// combine
Math.min(query(left), query(right));if r < lo or hi < l:
return float("inf")
min(self._query(node * 2, ...), self._query(node * 2 + 1, ...))if (r < lo || hi < l) return INT_MAX;
std::min(query(node * 2, ...), query(node * 2 + 1, ...));if (r < lo || hi < l) return Infinity;
Math.min(this.#query(node * 2, ...), this.#query(node * 2 + 1, ...));Same for max (-∞) and gcd (0, gcd(a,b) as combiner).
Segment tree = recursion skeleton + combiner + identity for your operation.
Common Mistakes
Allocating n instead of 4n.
tree size must be 4*n for the recursive layout — n under-allocates
because leaves sit at mixed depths.Wrong identity value.
Sum needs 0, but min needs +∞ and max -∞. Returning 0 from the disjoint case silently poisons min queries.
Recomputing instead of recombining after update.
After changing a leaf, every ancestor’s value must be rebuilt on the way back up — forget that and later queries read stale sums.
Complexity
| Operation | Time |
|---|---|
| Build | O(n) |
| Update | O(log n) |
| Query | O(log n) |
| Space | O(n) — allocate 4n |
Premium Content
Unlock Basic Segment Tree and all premium lessons with a subscription.
From ₹199.99/year — See plans