class SegTree {
int n;
int[] tree;
SegTree(int n) { this.n = n; tree = new int[2 * n]; }
void update(int i, int val) {
i += n; tree[i] = val;
for (i /= 2; i > 0; i /= 2)
tree[i] = tree[2*i] + tree[2*i+1];
}
int query(int l, int r) { // [l, r)
int res = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if ((l & 1) == 1) res += tree[l++];
if ((r & 1) == 1) res += tree[--r];
}
return res;
}
} type SegTree struct { n int; tree []int }
func NewSegTree(n int) *SegTree {
return &SegTree{n, make([]int, 2*n)}
}
func (s *SegTree) Update(i, val int) {
i += s.n; s.tree[i] = val
for i /= 2; i > 0; i /= 2 {
s.tree[i] = s.tree[2*i] + s.tree[2*i+1]
}
}
func (s *SegTree) Query(l, r int) int { // [l, r)
res := 0
for l, r = l+s.n, r+s.n; l < r; l, r = l/2, r/2 {
if l&1 == 1 { res += s.tree[l]; l++ }
if r&1 == 1 { r--; res += s.tree[r] }
}
return res
} class SegTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (2 * n)
def update(self, i, val):
i += self.n
self.tree[i] = val
while i > 1:
i //= 2
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def query(self, l, r): # [l, r)
res, l, r = 0, l + self.n, r + self.n
while l < r:
if l & 1: res += self.tree[l]; l += 1
if r & 1: r -= 1; res += self.tree[r]
l //= 2; r //= 2
return res struct SegTree { n: usize, tree: Vec<i32> }
impl SegTree {
fn new(n: usize) -> Self {
Self { n, tree: vec![0; 2 * n] }
}
fn update(&mut self, mut i: usize, val: i32) {
i += self.n; self.tree[i] = val;
i /= 2;
while i > 0 {
self.tree[i] = self.tree[2*i] + self.tree[2*i+1];
i /= 2;
}
}
fn query(&self, mut l: usize, mut r: usize) -> i32 {
let mut res = 0;
l += self.n; r += self.n;
while l < r {
if l & 1 == 1 { res += self.tree[l]; l += 1; }
if r & 1 == 1 { r -= 1; res += self.tree[r]; }
l /= 2; r /= 2;
}
res
}
} class SegTree {
n: number;
tree: number[];
constructor(n: number) {
this.n = n;
this.tree = new Array(2 * n).fill(0);
}
update(i: number, val: number): void {
i += this.n; this.tree[i] = val;
for (i = Math.floor(i / 2); i > 0; i = Math.floor(i / 2))
this.tree[i] = this.tree[2*i] + this.tree[2*i+1];
}
query(l: number, r: number): number { // [l, r)
let res = 0;
for (l += this.n, r += this.n; l < r;
l = Math.floor(l/2), r = Math.floor(r/2)) {
if (l & 1) res += this.tree[l++];
if (r & 1) res += this.tree[--r];
}
return res;
}
} Answer range queries and perform point or range updates in O(log n) using a binary tree where each node stores an aggregate over a subarray.
A segment tree is a binary tree where each node stores an aggregate value (sum, minimum, maximum, GCD, etc.) over a contiguous range of the original array. Leaf nodes correspond to individual array elements, and each internal node merges the results of its two children.
An array of n elements is represented as a complete binary tree of height O(log n). Each node covers a range [l, r] and stores the aggregate for that range. Queries and updates both take O(log n) by traversing from root to the relevant leaves.
Why not just use prefix sums? Prefix sums give O(1) range queries but O(n) point updates. A segment tree gives O(log n) for both queries and updates. When the array is mutable and you need many queries interleaved with updates, the segment tree is the go-to data structure.
Look for these recognition signals in the problem statement. If you spot one, a segment tree is very likely the intended approach.
"Range query" with "update"
"Count of elements" in a range
"Interval scheduling" or "skyline"
"Inversions" or "smaller after self"
The key clue: You need to repeatedly answer aggregate queries (sum, min, max, count) over arbitrary subranges of an array that is being modified between queries. Brute-force recomputation would be O(n) per query. The segment tree reduces each operation to O(log n) by decomposing any range into O(log n) pre-computed segments.
The simplest segment tree variant. Each node stores the sum of its range. Point updates modify a single leaf and propagate the change upward. Range queries decompose [l, r] into O(log n) nodes and sum them.
Build the tree bottom-up, then query sum(1, 3) and update index 2 to 7.
When you need to update an entire range at once (e.g., "add 5 to every element from index 2 to 6"), visiting each leaf would be O(n). Lazy propagation defers updates to child nodes until they are actually needed, keeping both range updates and range queries at O(log n).
Each node gets a "lazy" tag that records a pending update. When we visit a node during a query or update, we first push down any pending lazy value to its children before proceeding.
Choosing the variant: If you only need point updates (modify one element at a time), the basic segment tree without lazy propagation is simpler and sufficient. Use lazy propagation when the problem requires range updates (add a value to all elements in [l, r]) combined with range queries.
Here is the annotated Java template for a segment tree with point update and range sum query. The tree is stored in a flat array of size 4n.
int[] tree; int n; // Build the segment tree from array nums void build(int[] nums) { n = nums.length; tree = new int[4 * n]; buildHelper(1, 0, n - 1, nums); } void buildHelper(int node, int start, int end, int[] nums) { if (start == end) { tree[node] = nums[start]; // leaf node return; } int mid = (start + end) / 2; buildHelper(2 * node, start, mid, nums); // left child buildHelper(2 * node + 1, mid + 1, end, nums); // right child tree[node] = tree[2 * node] + tree[2 * node + 1]; // merge } // Point update: set nums[idx] = val void update(int node, int start, int end, int idx, int val) { if (start == end) { tree[node] = val; return; } int mid = (start + end) / 2; if (idx <= mid) update(2 * node, start, mid, idx, val); else update(2 * node + 1, mid + 1, end, idx, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; // re-merge } // Range query: sum of nums[l..r] int query(int node, int start, int end, int l, int r) { if (r < start || end < l) return 0; // no overlap if (l <= start && end <= r) return tree[node]; // total overlap int mid = (start + end) / 2; return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r); // partial overlap }
type SegTree struct { tree []int n int } // Build the segment tree from slice nums func NewSegTree(nums []int) *SegTree { n := len(nums) st := &SegTree{tree: make([]int, 4*n), n: n} st.build(1, 0, n-1, nums) return st } func (st *SegTree) build(node, start, end int, nums []int) { if start == end { st.tree[node] = nums[start] // leaf node return } mid := (start + end) / 2 st.build(2*node, start, mid, nums) // left child st.build(2*node+1, mid+1, end, nums) // right child st.tree[node] = st.tree[2*node] + st.tree[2*node+1] // merge } // Point update: set nums[idx] = val func (st *SegTree) Update(node, start, end, idx, val int) { if start == end { st.tree[node] = val return } mid := (start + end) / 2 if idx <= mid { st.Update(2*node, start, mid, idx, val) } else { st.Update(2*node+1, mid+1, end, idx, val) } st.tree[node] = st.tree[2*node] + st.tree[2*node+1] // re-merge } // Range query: sum of nums[l..r] func (st *SegTree) Query(node, start, end, l, r int) int { if r < start || end < l { return 0 // no overlap } if l <= start && end <= r { return st.tree[node] // total overlap } mid := (start + end) / 2 return st.Query(2*node, start, mid, l, r) + st.Query(2*node+1, mid+1, end, l, r) // partial overlap }
class SegmentTree: def __init__(self, nums: list[int]): self.n = len(nums) self.tree = [0] * (4 * self.n) self._build(1, 0, self.n - 1, nums) # Build the segment tree from array nums def _build(self, node: int, start: int, end: int, nums: list[int]): if start == end: self.tree[node] = nums[start] # leaf node return mid = (start + end) // 2 self._build(2 * node, start, mid, nums) # left child self._build(2 * node + 1, mid + 1, end, nums) # right child self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1] # Point update: set nums[idx] = val def update(self, node: int, start: int, end: int, idx: int, val: int): if start == end: self.tree[node] = val return mid = (start + end) // 2 if idx <= mid: self.update(2 * node, start, mid, idx, val) else: self.update(2 * node + 1, mid + 1, end, idx, val) self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1] # Range query: sum of nums[l..r] def query(self, node: int, start: int, end: int, l: int, r: int) -> int: if r < start or end < l: return 0 # no overlap if l <= start and end <= r: return self.tree[node] # total overlap mid = (start + end) // 2 return self.query(2 * node, start, mid, l, r) \ + self.query(2 * node + 1, mid + 1, end, l, r)
struct SegTree { tree: Vec<i32>, n: usize, } impl SegTree { // Build the segment tree from slice nums fn new(nums: &[i32]) -> Self { let n = nums.len(); let mut st = SegTree { tree: vec![0; 4 * n], n }; st.build(1, 0, n - 1, nums); st } fn build(&mut self, node: usize, start: usize, end: usize, nums: &[i32]) { if start == end { self.tree[node] = nums[start]; // leaf node return; } let mid = (start + end) / 2; self.build(2 * node, start, mid, nums); // left child self.build(2 * node + 1, mid + 1, end, nums); // right child self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]; // merge } // Point update: set nums[idx] = val fn update(&mut self, node: usize, start: usize, end: usize, idx: usize, val: i32) { if start == end { self.tree[node] = val; return; } let mid = (start + end) / 2; if idx <= mid { self.update(2 * node, start, mid, idx, val); } else { self.update(2 * node + 1, mid + 1, end, idx, val); } self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]; // re-merge } // Range query: sum of nums[l..r] fn query(&self, node: usize, start: usize, end: usize, l: usize, r: usize) -> i32 { if r < start || end < l { return 0; // no overlap } if l <= start && end <= r { return self.tree[node]; // total overlap } let mid = (start + end) / 2; self.query(2 * node, start, mid, l, r) + self.query(2 * node + 1, mid + 1, end, l, r) // partial overlap } }
let tree: number[]; let n: number; // Build the segment tree from array nums function build(nums: number[]): void { n = nums.length; tree = new Array(4 * n).fill(0); buildHelper(1, 0, n - 1, nums); } function buildHelper(node: number, start: number, end: number, nums: number[]): void { if (start === end) { tree[node] = nums[start]; // leaf node return; } const mid = Math.floor((start + end) / 2); buildHelper(2 * node, start, mid, nums); // left child buildHelper(2 * node + 1, mid + 1, end, nums); // right child tree[node] = tree[2 * node] + tree[2 * node + 1]; // merge } // Point update: set nums[idx] = val function update(node: number, start: number, end: number, idx: number, val: number): void { if (start === end) { tree[node] = val; return; } const mid = Math.floor((start + end) / 2); if (idx <= mid) update(2 * node, start, mid, idx, val); else update(2 * node + 1, mid + 1, end, idx, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; // re-merge } // Range query: sum of nums[l..r] function query(node: number, start: number, end: number, l: number, r: number): number { if (r < start || end < l) return 0; // no overlap if (l <= start && end <= r) return tree[node]; // total overlap const mid = Math.floor((start + end) / 2); return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r); // partial overlap }
int[] lazy; // initialize to 0 void pushDown(int node, int start, int end) { if (lazy[node] != 0) { int mid = (start + end) / 2; applyLazy(2 * node, start, mid, lazy[node]); applyLazy(2 * node + 1, mid + 1, end, lazy[node]); lazy[node] = 0; } } void applyLazy(int node, int start, int end, int val) { tree[node] += val * (end - start + 1); // sum aggregate lazy[node] += val; // accumulate for children }
// lazy []int — initialize to 0 alongside tree func (st *SegTree) pushDown(node, start, end int) { if st.lazy[node] != 0 { mid := (start + end) / 2 st.applyLazy(2*node, start, mid, st.lazy[node]) st.applyLazy(2*node+1, mid+1, end, st.lazy[node]) st.lazy[node] = 0 } } func (st *SegTree) applyLazy(node, start, end, val int) { st.tree[node] += val * (end - start + 1) // sum aggregate st.lazy[node] += val // accumulate for children }
lazy: list[int] # initialize to 0 def push_down(self, node: int, start: int, end: int): if self.lazy[node] != 0: mid = (start + end) // 2 self._apply_lazy(2 * node, start, mid, self.lazy[node]) self._apply_lazy(2 * node + 1, mid + 1, end, self.lazy[node]) self.lazy[node] = 0 def _apply_lazy(self, node: int, start: int, end: int, val: int): self.tree[node] += val * (end - start + 1) # sum aggregate self.lazy[node] += val # accumulate for children
// lazy: Vec<i32> — initialize to 0 alongside tree impl SegTree { fn push_down(&mut self, node: usize, start: usize, end: usize) { if self.lazy[node] != 0 { let mid = (start + end) / 2; let lz = self.lazy[node]; self.apply_lazy(2 * node, start, mid, lz); self.apply_lazy(2 * node + 1, mid + 1, end, lz); self.lazy[node] = 0; } } fn apply_lazy(&mut self, node: usize, start: usize, end: usize, val: i32) { self.tree[node] += val * (end - start + 1) as i32; // sum aggregate self.lazy[node] += val; // accumulate for children } }
let lazy: number[]; // initialize to 0 function pushDown(node: number, start: number, end: number): void { if (lazy[node] !== 0) { const mid = Math.floor((start + end) / 2); applyLazy(2 * node, start, mid, lazy[node]); applyLazy(2 * node + 1, mid + 1, end, lazy[node]); lazy[node] = 0; } } function applyLazy(node: number, start: number, end: number, val: number): void { tree[node] += val * (end - start + 1); // sum aggregate lazy[node] += val; // accumulate for children }
Why 4n space? The tree array needs at most 4n slots. In the worst case, when n is not a power of 2, the last level of the implicit binary tree may have gaps. Using 4n guarantees no out-of-bounds access. For n that is a power of 2, 2n would suffice.
Let us trace through building a segment tree from [1, 3, 5, 7, 9, 2], performing a range query, and then a point update.
Building a sum segment tree, then querying sum(2, 4) and updating index 3 to 1.
| OPERATION | PATH | NODES VISITED | RESULT |
|---|---|---|---|
| Build | Bottom-up | All 11 nodes | Root = 27 |
| query(2, 4) | root → both children | [0,5] → [0,2]: [2,2]✓ · [3,5]: [3,4]✓ | 5 + 16 = 21 |
| update(3, 1) | root → right → left → leaf | [0,5] → [3,5] → [3,4] → [3,3] | leaf 7→1, propagate -6 up |
| query(2, 4) again | Same path | [2,2]=5 + [3,4]=10 | 5 + 10 = 15 |
Notice the efficiency: The query sum(2, 4) does not visit all 3 leaves individually. It picks up node [2,2] (a single leaf) and node [3,4] (an internal node covering two elements) for a total of just 2 contributions. For larger arrays, the savings are dramatic: a range of 1000 elements might be covered by only ~20 nodes.
These are classic LeetCode problems that use the segment tree pattern, listed in rough order of difficulty.
Practice tip: Start with #307 which is the direct application of the basic segment tree template. Then tackle #315 which requires a creative twist: process the array from right to left and use the segment tree to count how many previously-seen elements are smaller. #218 and #732 use the segment tree for interval/event-based problems.
Enter an array, build a segment tree, then perform point updates and range sum queries. Watch the tree structure with highlighted nodes during each operation.
Build O(n): Each of the n leaves is visited once, and there are n-1 internal nodes. The total work at each level is proportional to the number of nodes at that level, which sums to O(n) across all levels.
Query O(log n): At each level of the tree, at most 2 nodes have their ranges partially overlapping with the query range. All other nodes are either fully inside (returned immediately) or fully outside (pruned). This means we visit at most O(log n) nodes total.
Update O(log n): A point update follows a single root-to-leaf path, updating the aggregate at each level. The tree has O(log n) levels.
Space: The tree array uses O(n) space (specifically 4n slots). With lazy propagation, an additional O(n) lazy array is needed.
Comparison with alternatives: A Fenwick tree (Binary Indexed Tree) also achieves O(log n) per operation for prefix sums but is harder to extend to non-invertible operations like min/max. A segment tree is more versatile: it handles any associative merge function and supports lazy propagation for range updates.
Divide and conquer on ranges. The segment tree recursively splits the array into halves. Each node owns a range [l, r] and stores the aggregate for that range. This divide-and-conquer structure is what enables O(log n) queries and updates.
Three cases in every query. When querying [ql, qr] at a node covering [l, r]: (1) no overlap → return identity, (2) total overlap → return node value, (3) partial overlap → recurse into both children and merge. Master this three-way check and you can implement any segment tree.
Lazy propagation defers work. For range updates, do not visit every leaf. Store a pending update at the highest node that fully covers the update range, and push it down only when needed. This keeps range updates at O(log n).
Works with any associative merge. Sum, min, max, GCD, bitwise OR, count of zeros, matrix products. As long as the merge operation is associative, the segment tree structure applies. Change the merge function and identity element to adapt.
Use 4n space for safety. The flat array representation uses indices 1 to ~4n. Children of node i are at 2i and 2i+1. This implicit representation avoids pointer overhead and is cache-friendly, making it fast in practice.