Segment Trees & Fenwick Trees

What you'll learn

• The Problem: Range Queries with Updates

  Consider an array of n elements. You need to repeatedly: 1. Query an aggregate (sum, min, max) over a range [l, r] 2. Update individual elements (or ranges) of the array This combination arises constantly: stock price tracking, game lead…

• Naive Approaches and Their Limits

  | Approach | Query Time | Update Time | Space | |----------|-----------|-------------|-------| | Brute-force scan | O(n) | O(1) | O(n) | | Prefix sum array | O(1) | O(n) | O(n) | | Segment Tree | O(log n) | O(log n) | O(n) | | Fenwick Tr…

• Segment Tree

• Core Idea

  A segment tree is a binary tree where: - Each leaf stores one element of the array - Each internal node stores the aggregate (sum, min, max, etc.) of its children's ranges - The root stores the aggregate for the entire array

• Structure Diagram

  For array [1, 3, 5, 7, 9, 11]: Each node covers a contiguous range. The tree has O(n) nodes total.

• Why Size 4n for Array Storage?

  When implementing a segment tree using a flat array (index-based, no pointers): - A complete binary tree with n leaves needs at most 2n - 1 nodes - But n may not be a power of 2, so we pad to the next power of 2 - For the worst case (n =…

• Build Operation - O(n)

  Build the tree bottom-up: leaves hold array values, each parent merges its two children. There are at most 2n-1 nodes, each visited exactly once during construction, giving O(n) build time. The recursion starts at the root with range [0,…

• Query Operation - O(log n)

  At each level of the tree, at most 2 nodes can be partially overlapping (one on the left boundary, one on the right boundary). All other nodes at that level are either fully contained (returned immediately) or fully outside (pruned). The…

• Point Update - O(log n)

  Only nodes on the path from the leaf to the root need updating. The tree height is log(n), so exactly log(n) + 1 nodes are visited. To update index i to value val: - Navigate from root to the leaf at index i - Update the leaf - Propagate…

• Lazy Propagation for Range Updates

  Problem: If we need to update all elements in range [l, r] (e.g., add 5 to each), doing individual point updates gives O(n log n). Can we do better? Lazy Propagation Idea: Each node gets a "lazy" tag storing a pending operation. When we…

• Complete Segment Tree Implementation

• Compact Iterative Segment Tree (2N Array)

  An alternative implementation uses a flat array of size 2n. Leaves are stored at indices [n, 2n-1] and internal nodes at [1, n-1]. This eliminates recursion overhead. The flattened tree stores leaves at [size, 2size-1] and internal nodes…

• Fenwick Tree (Binary Indexed Tree)

• Core Concept

  A Fenwick tree stores partial sums in a clever way using the binary representation of indices. Each position i is responsible for a range of elements determined by the lowest set bit of i. The lowest set bit of i is: i & (-i)

• Visual Representation

• Prefix Sum Query - O(log n)

  Each step removes the lowest set bit of i. Since i has at most log(n) bits, the loop runs at most log(n) times. To compute prefix sum up to index i: - Start at index i - Add tree[i] to result - Remove the lowest set bit: i -= i & (-i) -…

• Point Update - O(log n)

  Each step adds the lowest set bit, which at least doubles the value of the lowest set bit. Since we stop at n, there are at most log(n) iterations. To add delta to index i: - Start at index i - Add delta to tree[i] - Add the lowest set b…

• Range Sum Query

  To get sum of range [l, r]:

• Implementation

  ---

• Comparison Table

  | Feature | Prefix Sum | Fenwick Tree | Segment Tree | |---------|-----------|-------------|-------------| | Build time | O(n) | O(n) | O(n) | | Point update | O(n) | O(log n) | O(log n) | | Range query (sum) | O(1) | O(log n) | O(log n)…

• When to Use Each

• Use Prefix Sum Array When:

  - Array is static (no updates after construction) - You only need range sum queries - You want O(1) query time

• Use Fenwick Tree When:

  - You need point updates + range sum queries - The operation is addition/subtraction (invertible) - You want minimal code and good constant factors - Memory is a concern (half the space of segment tree)

• Use Segment Tree When:

  - You need any associative operation (min, max, GCD, XOR, etc.) - You need range updates (lazy propagation) - You need to answer more complex queries (k-th element, etc.) - Flexibility is more important than constant factors ---

• Common Interview Patterns

• Pattern 1: Count Inversions

  Use a Fenwick tree to count how many previously-seen elements are greater than the current element. Time: O(n log n), space: O(n). Sample Input / Output Input: arr = [5, 2, 6, 1, 3] Output: 7 — inversions are (5,2), (5,1), (5,3), (2,1),…

• Pattern 2: Range Sum with Point Updates

  Classic Fenwick tree / segment tree application. Time: O(n + (Q+U)log n), space: O(n) for Fenwick or O(4n) for segment tree. Sample Input / Output Input: arr = [1, 3, 5, 7, 9], operations: update(2, 10), query(1, 3) Output: after update,…

• Pattern 3: Range Minimum Query with Updates

  Sample Input / Output Input: arr = [5, 2, 9, 1, 7, 4], ops: query(1, 4), update(3, 0), query(1, 4) Output: 1 (min of [2,9,1,7]), then 0 (after setting index 3 to 0) Input: arr = [3, 8, 2, 6, 1], ops: query(0, 4), update(4, 10), query(0,…

• Pattern 4: Coordinate Compression + Fenwick

  Sample Input / Output Input: nums = [109, 3, 109 - 7, 42] (values span 0…10⁹ but only 4 distinct) Compressed: {3: 1, 42: 2, 109 - 7: 3, 109: 4} → work over ranks 1..4 instead of 10⁹ indices Output: any rank-based Fenwick query (e.g. coun…

• Pattern 5: 2D Fenwick Tree

  Sample Input / Output Input: matrix = [[3,0,1],[0,5,0],[2,0,4]], ops: update(1,1, +2), sumRegion(0,0, 2,2) Output: after update matrix[1][1] becomes 7; region sum 3+0+1+0+7+0+2+0+4 = 17 Input: matrix = [[1,2],[3,4]], ops: sumRegion(0,0,…

• Complexity Summary

  | Operation | Segment Tree | Fenwick Tree | |-----------|-------------|-------------| | Build | O(n) | O(n) | | Point update | O(log n) | O(log n) | | Point query | O(log n) | O(log n) | | Range query | O(log n) | O(log n) | | Range upda…

• Key Takeaways

  1. Segment tree is the Swiss Army knife of range queries - handles any associative operation with O(log n) query and update 2. Fenwick tree is the scalpel - simpler, faster constant, but limited to invertible operations (primarily sums)…

• Practice Problems Walkthrough

• Problem: Range Sum Query - Mutable (LC 307)

  Given an array of integers, support two operations: update an element at index i, and query the sum over range [l, r]. Sample Input / Output Input: arr = [1, 3, 5, 7, 9, 11], operations: update(2, 10), query(1, 4) Output: After update, q…

• Problem: Range Minimum Query with Point Updates

  Given an array of integers, support two operations: update an element at index i, and query the minimum value over range [l, r]. Sample Input / Output Input: arr = [5, 2, 9, 1, 7, 4], operations: query(1, 4), update(3, 0), query(1, 4) Ou…

• Problem: Count of Smaller Numbers After Self (LC 315)

  Given an array of integers, for each element, count how many elements to its right are smaller than it. Sample Input / Output Input: nums = [5, 2, 6, 1] Output: [2, 1, 1, 0] — (5 has [2,1] smaller; 2 has [1]; 6 has [1]; 1 has none) Input…

• Problem: Range Add Query (LC 370)

  Given an array initialized to all zeros, support range updates (add val to all elements in [l, r]) and point queries (return arr[i]). Sample Input / Output Input: length = 5, operations: update(1, 3, 2), update(2, 4, 3), query(2) Output:…