Answer range queries and handle point updates on arrays — both in O(log n). The go-to structures for competitive programming and database internals.
AdvancedSay you have an array of numbers and you keep getting asked: "what's the sum from index 3 to index 7?" You could loop through and add them up each time — that's O(n) per query. If you're getting thousands of queries on a million-element array, that's way too slow.
A prefix sum array (a precomputed array where element i holds the sum of all elements from 0 to i) fixes the query to O(1): sum(L, R) = prefix[R] - prefix[L-1]. But what if the array changes? Updating one element means recomputing the entire prefix sum — back to O(n).
A segment tree is a binary tree (a tree where each node has at most two children) where each node stores a pre-computed answer for a segment (a contiguous range) of the array. The root covers the entire array [0, n-1]. Its two children split the range in half: [0, mid] and [mid+1, n-1]. This splitting continues recursively until each leaf corresponds to a single array element.
This gives you O(log n) for both queries AND updates. You never visit more than about 2·log(n) nodes for any operation — you combine pre-computed results from segments that together cover your query range.
Segment trees were introduced by Jon Bentley in 1977 in the context of computational geometry — specifically, for counting how many line segments contain a given point. The structure was later generalized to handle arbitrary associative operations (operations where (a⊕b)⊕c = a⊕(b⊕c), like addition, min, max, GCD, XOR) over array ranges. They became a staple of competitive programming in the 2000s when online judge platforms made range query problems ubiquitous.
A Binary Indexed Tree (BIT), also called a Fenwick Tree (named after Peter Fenwick, who described it in 1994), solves the same prefix-sum problem with a much simpler implementation. It uses a clever trick with the binary representation (the base-2 encoding) of array indices to maintain partial sums.
Trade-off: BITs are simpler to code (about 10 lines), use less memory (array of size n+1), and have smaller constant factors. But segment trees are more flexible — they handle min/max queries, support lazy propagation (a technique for deferring range updates to avoid updating every element individually), and can be extended to 2D, persistent, and merge-sort variants.
Start with your array of n elements. The tree has at most 4n nodes (a safe upper bound). Each leaf node (a node with no children) stores one array element. Each internal node (a node with children) stores the combined value of its two children. For a sum tree, that's left + right. For a min tree, it's min(left, right).
Building works bottom-up: fill the leaves with array values, then compute each parent as the combination of its children. This takes O(n) time — you visit each node once.
Indexing convention: The root is at index 1. For any node at index i, its left child is at 2*i and its right child is at 2*i + 1. This lets you store the tree in a flat array without explicit pointers — the same trick used by binary heaps.
To change array[idx] to a new value: start at the root and recurse down to the leaf at position idx. Update the leaf, then propagate the change back up — each ancestor recomputes itself from its two children. You touch one node per level, so it's O(log n).
To query range [L, R], start at the root (which covers [0, n-1]). At each node covering range [lo, hi]:
This visits at most O(log n) nodes because at each level, at most two nodes are partially overlapping — all others are either fully inside (returned immediately) or fully outside (pruned).
What if you need to update an entire range — "add 5 to every element from index 3 to 7"? Without lazy propagation, you'd update each of the 5 elements individually: O(n log n). Lazy propagation defers the update: mark the node with a "pending" value and only push it down to children when needed. This gives O(log n) for range updates.
The core idea: when a range update fully covers a node's range, mark it as "lazy" instead of recursing into children. When you later need to query or update a child, push the pending update down first. It's procrastination as an optimization strategy.
A Fenwick Tree stores partial sums in a clever way. Index i in the BIT array is responsible for a range whose length equals the lowest set bit (the rightmost 1-bit in the binary representation) of i.
For example, index 12 (binary 1100) has lowest set bit 4 (binary 100), so BIT[12] stores the sum of 4 elements: arr[9] through arr[12].
Prefix sum query: Start at index i. Add BIT[i] to your sum. Remove the lowest set bit: i -= i & (-i). Repeat until i is 0. Each step hops to a non-overlapping partial sum.
Point update: Start at index i. Add the delta to BIT[i]. Add the lowest set bit: i += i & (-i). Repeat until i exceeds n. Each step updates the next "responsible" node.
The key bit-manipulation operation: i & (-i) isolates the lowest set bit. In two's complement, -i flips all bits and adds 1, so i & (-i) gives you exactly the rightmost 1-bit.
The tree shows pre-computed range sums. Click "Query" to highlight the segments used to answer a range query. Click "Update" to change a value and watch the tree propagate changes upward.
| Operation | Segment Tree | Fenwick Tree (BIT) | Prefix Sum Array |
|---|---|---|---|
| Build | O(n) | O(n log n) | O(n) |
| Point Update | O(log n) | O(log n) | O(n) — must rebuild prefix sums |
| Range Query | O(log n) | O(log n) | O(1) |
| Range Update (lazy) | O(log n) | O(log n)* | O(n) |
| Space | O(4n) | O(n) | O(n) |
*BIT range updates use a technique with two BITs. Segment trees with lazy propagation are more straightforward for this — and much easier to implement correctly under interview pressure.
class SegmentTree:
"""Segment tree for range sum queries with point updates.
Uses 1-indexed array: root at index 1, children of i at 2i and 2i+1."""
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n) # 4n is a safe upper bound on node count
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr, node, lo, hi):
"""Recursively build the tree. O(n) total."""
if lo == hi:
# Leaf node: store the array element directly
self.tree[node] = arr[lo]
return
mid = (lo + hi) // 2
self._build(arr, 2 * node, lo, mid) # Build left child
self._build(arr, 2 * node + 1, mid + 1, hi) # Build right child
# Internal node: combine children
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, idx, val, node=1, lo=0, hi=None):
"""Set arr[idx] = val. Propagate change up to root. O(log n)."""
if hi is None: hi = self.n - 1
if lo == hi:
# Reached the leaf for arr[idx]
self.tree[node] = val
return
mid = (lo + hi) // 2
if idx <= mid:
self.update(idx, val, 2 * node, lo, mid) # Go left
else:
self.update(idx, val, 2 * node + 1, mid + 1, hi) # Go right
# Recompute this node from its updated children
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, l, r, node=1, lo=0, hi=None):
"""Sum of arr[l..r] inclusive. O(log n).
Three cases at each node:
- Total overlap → return stored value
- No overlap → return 0 (identity for addition)
- Partial overlap → recurse both children"""
if hi is None: hi = self.n - 1
if r < lo or hi < l:
return 0 # No overlap — this segment doesn't intersect [l, r]
if l <= lo and hi <= r:
return self.tree[node] # Total overlap — use precomputed value
mid = (lo + hi) // 2
return (self.query(l, r, 2 * node, lo, mid) +
self.query(l, r, 2 * node + 1, mid + 1, hi))
# Usage
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.query(1, 3)) # 15 (3 + 5 + 7)
print(st.query(0, 5)) # 36 (sum of entire array)
st.update(2, 10) # Change arr[2] from 5 to 10
print(st.query(1, 3)) # 20 (3 + 10 + 7)
print(st.query(0, 5)) # 41 (1 + 3 + 10 + 7 + 9 + 11)class LazySegTree:
"""Segment tree with lazy propagation.
Supports: range add update + range sum query, both O(log n).
The 'lazy' array stores pending additions that haven't been pushed
down to children yet. This is how we avoid O(n) range updates."""
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n) # Pending updates
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, 2 * node, lo, mid)
self._build(arr, 2 * node + 1, mid + 1, hi)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def _push_down(self, node, lo, hi):
"""Push pending lazy update to children. Called before accessing children."""
if self.lazy[node] != 0:
mid = (lo + hi) // 2
# Apply pending update to left child
self.tree[2 * node] += self.lazy[node] * (mid - lo + 1)
self.lazy[2 * node] += self.lazy[node]
# Apply pending update to right child
self.tree[2 * node + 1] += self.lazy[node] * (hi - mid)
self.lazy[2 * node + 1] += self.lazy[node]
# Clear this node's lazy value
self.lazy[node] = 0
def range_update(self, l, r, val, node=1, lo=0, hi=None):
"""Add val to every element in arr[l..r]. O(log n)."""
if hi is None: hi = self.n - 1
if r < lo or hi < l:
return # No overlap
if l <= lo and hi <= r:
# Total overlap — apply lazily instead of recursing
self.tree[node] += val * (hi - lo + 1)
self.lazy[node] += val
return
self._push_down(node, lo, hi) # Must push before recursing
mid = (lo + hi) // 2
self.range_update(l, r, val, 2 * node, lo, mid)
self.range_update(l, r, val, 2 * node + 1, mid + 1, hi)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, l, r, node=1, lo=0, hi=None):
"""Sum of arr[l..r] inclusive. O(log n)."""
if hi is None: hi = self.n - 1
if r < lo or hi < l:
return 0
if l <= lo and hi <= r:
return self.tree[node]
self._push_down(node, lo, hi) # Push lazy before querying children
mid = (lo + hi) // 2
return (self.query(l, r, 2 * node, lo, mid) +
self.query(l, r, 2 * node + 1, mid + 1, hi))
# Usage
arr = [1, 3, 5, 7, 9, 11]
lst = LazySegTree(arr)
print(lst.query(1, 3)) # 15
lst.range_update(1, 4, 10) # Add 10 to indices 1,2,3,4
print(lst.query(1, 3)) # 45 (13 + 15 + 17)
print(lst.query(0, 5)) # 76 (1 + 13 + 15 + 17 + 19 + 11)class FenwickTree {
/**
* Binary Indexed Tree for prefix sum queries + point updates.
* Simpler than segment tree, but limited to operations with an inverse
* (sum, XOR — NOT min/max).
* Uses 1-indexed array internally.
*/
constructor(n) {
this.n = n;
this.bit = new Array(n + 1).fill(0);
}
// Build from an existing array
static fromArray(arr) {
const ft = new FenwickTree(arr.length);
for (let i = 0; i < arr.length; i++) {
ft.update(i, arr[i]);
}
return ft;
}
// Add delta to index i (0-indexed input, converted to 1-indexed)
update(i, delta) {
i++; // Convert to 1-indexed
while (i <= this.n) {
this.bit[i] += delta;
i += i & (-i); // Move to next responsible index
// i & (-i) isolates the lowest set bit
// Adding it moves to the next node that covers this index
}
}
// Prefix sum [0, i] inclusive (0-indexed input)
prefixSum(i) {
i++; // Convert to 1-indexed
let sum = 0;
while (i > 0) {
sum += this.bit[i];
i -= i & (-i); // Strip lowest set bit → jump to non-overlapping range
}
return sum;
}
// Range sum [l, r] inclusive (0-indexed)
rangeSum(l, r) {
// sum(l..r) = prefix(r) - prefix(l-1)
return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
}
}
// Usage
const ft = FenwickTree.fromArray([1, 3, 5, 7, 9, 11]);
console.log(ft.rangeSum(1, 3)); // 15 (3 + 5 + 7)
ft.update(2, 5); // Add 5 to index 2 (5 → 10)
console.log(ft.rangeSum(1, 3)); // 20 (3 + 10 + 7)push_down() before accessing children in both query AND update functions. Forgetting this in one of the two operations produces subtle, hard-to-debug wrong answers.Gaming platforms and contest sites need to answer questions like "how many players scored between 500 and 800?" and "what rank is this player?" in real-time as scores change. A Fenwick Tree handles this beautifully.
class Leaderboard:
"""Live leaderboard using a BIT (Fenwick Tree) for rank queries.
Idea: Use a BIT indexed by score. BIT[score] = number of players
with exactly that score. Prefix sum gives "how many players have
score <= X", which directly tells you a player's rank.
This is essentially the technique used in competitive programming
for "Count of Smaller Numbers After Self" (LC 315).
"""
def __init__(self, max_score=1000):
self.max_score = max_score
self.bit = [0] * (max_score + 2) # 1-indexed BIT
self.player_scores = {} # player_id → current score
self.total_players = 0
def _update(self, i, delta):
i += 1 # 1-indexed
while i <= self.max_score + 1:
self.bit[i] += delta
i += i & (-i)
def _prefix_count(self, i):
"""How many players have score <= i?"""
i += 1 # 1-indexed
count = 0
while i > 0:
count += self.bit[i]
i -= i & (-i)
return count
def add_player(self, player_id, score):
"""Add a player or update their score."""
if player_id in self.player_scores:
# Remove old score first
old_score = self.player_scores[player_id]
self._update(old_score, -1)
else:
self.total_players += 1
self.player_scores[player_id] = score
self._update(score, 1)
def get_rank(self, player_id):
"""Get player's rank (1 = highest score). O(log max_score)."""
if player_id not in self.player_scores:
return -1
score = self.player_scores[player_id]
# Players with higher score + 1 = this player's rank
players_above = self.total_players - self._prefix_count(score)
return players_above + 1
def count_in_range(self, low_score, high_score):
"""How many players scored between low and high (inclusive)?"""
return (self._prefix_count(high_score) -
(self._prefix_count(low_score - 1) if low_score > 0 else 0))
# Demo: gaming tournament
board = Leaderboard(max_score=100)
board.add_player("alice", 85)
board.add_player("bob", 72)
board.add_player("charlie", 91)
board.add_player("dave", 85)
board.add_player("eve", 68)
print(f"Charlie's rank: {board.get_rank('charlie')}") # 1 (highest)
print(f"Alice's rank: {board.get_rank('alice')}") # 2 (tied with Dave)
print(f"Players scoring 70-90: {board.count_in_range(70, 90)}") # 3
# Score update! Bob levels up
board.add_player("bob", 95)
print(f"\nAfter Bob's update:")
print(f"Bob's rank: {board.get_rank('bob')}") # 1
print(f"Charlie's rank: {board.get_rank('charlie')}") # 2The classic use case. An array changes over time, and you need sums of arbitrary ranges after each change. Both segment tree and BIT work. LeetCode 307 is the textbook version — it's literally called "Range Sum Query - Mutable."
Process elements right-to-left, inserting each value into a BIT. Query the BIT to count how many previously-inserted values are smaller. This requires coordinate compression (mapping values to their rank among all values to keep the BIT size manageable). Solves "Count of Smaller Numbers After Self" (LC 315).
Each segment tree node stores a sorted list of elements in its range. This lets you answer "how many elements in [L, R] are ≤ K?" in O(log²n) time. Overkill for most interviews, but shows up in competitive programming and can impress if you mention it as a follow-up.
| Problem | Difficulty | Key Idea |
|---|---|---|
| 307. Range Sum Query — Mutable | Medium | Textbook segment tree / BIT — the starting problem |
| 315. Count of Smaller Numbers After Self | Hard | BIT with coordinate compression — process right to left |
| 308. Range Sum Query 2D — Mutable | Hard | 2D BIT (BIT of BITs) |
| 729. My Calendar I | Medium | Segment tree with lazy propagation for interval booking |
| 327. Count of Range Sum | Hard | BIT on prefix sums with coordinate compression |
| 493. Reverse Pairs | Hard | BIT or merge sort — count pairs where nums[i] > 2·nums[j] |