Segment Trees and Binary Indexed Trees

Chapter 14: Segment Trees and Binary Indexed Trees

When you need to perform a large number of range queries and point/range updates on an array, naive approaches are always linear on one end—either O(n) for queries or O(n) for updates. Segment Trees and Binary Indexed Trees (BIT / Fenwick Trees) are two data structures specifically designed for this class of problems, reducing both operations to O(log n).

These two data structures appear with extremely high frequency in competitive programming, technical interviews, and engineering practice. Understanding them is not just about learning an "advanced data structure"—it is an excellent case study of how "trading space for time" and "applying divide-and-conquer thinking to data structure design" actually works.

Level 1 · What You Need to Know

14.1 Starting from the Problem: Why Do We Need Segment Trees

Consider this scenario: you have an array nums of length n, and you need to repeatedly perform two types of operations:

1. Range query: compute the sum (or max, min, etc.) of nums[l..r]
2. Point update: change nums[i] to some new value

Core Insight: The reason a segment tree achieves O(log n) on both ends is that it recursively bisects the interval [0, n-1] into a complete binary tree. Each node stores the aggregated information (e.g., sum) of its corresponding interval. When you modify an element, you only need to update nodes along the leaf-to-root path—O(log n) nodes. When you query an interval, at most O(log n) nodes are needed to cover the entire query range.

14.2 Structure of a Segment Tree

A segment tree is a binary tree with the following structure:

• The root node represents the entire array interval [0, n-1]
• Each internal node represents an interval [l, r]; its left child represents [l, mid] and its right child represents [mid+1, r] (where mid = (l + r) // 2)
• Leaf nodes represent individual elements [i, i]
• Each node stores the aggregated value of its corresponding interval

For an array of length n, the segment tree has these properties:

• Number of leaves = n
• Total nodes ≤ 4n (actually 2 × 2^⌈log₂n⌉ - 1, but allocating 4n is safe and simple)
• Height = ⌈log₂n⌉

Why allocate 4n space? This is a common point of confusion. A segment tree is close to a complete binary tree. If n is exactly a power of 2, we need 2n - 1 nodes. But if n is not a power of 2, the last level has gaps, and the upper bound becomes 4n. In practice, allocating 4n is the safe and simple approach.

14.3 Array-Based Segment Tree Implementation

The most common implementation uses an array to simulate a complete binary tree (similar to heap storage):

• Root node at index 1
• Left child of node i at index 2*i
• Right child of node i at index 2*i + 1
• Parent of node i at index i // 2

class SegmentTree:
    """Basic Segment Tree — supports point update and range sum query"""
    
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)  # Allocate 4n space
        if self.n > 0:
            self._build(nums, 1, 0, self.n - 1)
    
    def _build(self, nums, node, start, end):
        """Recursive build: aggregate bottom-up"""
        if start == end:
            # Leaf node: store original value directly
            self.tree[node] = nums[start]
            return
        mid = (start + end) // 2
        self._build(nums, 2 * node, start, mid)       # Build left subtree
        self._build(nums, 2 * node + 1, mid + 1, end) # Build right subtree
        # Internal node: aggregate from children
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def update(self, idx, val):
        """Point update: set nums[idx] to val"""
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            # Reached leaf node, modify directly
            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)
        # Update parent on backtrack
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, l, r):
        """Range query: compute sum of nums[l..r]"""
        return self._query(1, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        # Current node's interval is fully contained in query — return directly
        if l <= start and end <= r:
            return self.tree[node]
        # Current node's interval has no intersection with query
        if end < l or start > r:
            return 0
        # Partial overlap — recurse into children
        mid = (start + end) // 2
        left_sum = self._query(2 * node, start, mid, l, r)
        right_sum = self._query(2 * node + 1, mid + 1, end, l, r)
        return left_sum + right_sum

Understanding the Recursive Process:

1. _build: constructs bottom-up. Each leaf stores the original value; each parent equals the sum of its children. Time: O(n).
2. _update: traverses root-to-leaf to find and modify the target, then backtracks updating all ancestors. Time: O(log n).
3. _query: from the root downward—if a node's interval is fully contained in the query range, return immediately; otherwise recurse. At most a constant number of nodes per level are visited. Time: O(log n).

Why is query O(log n)? The key observation is: for any query interval [l, r], at each level of the tree, at most two nodes are "partially covered" (one at the left boundary, one at the right). All other visited nodes are "fully covered" and return immediately. Thus the total number of visited nodes is at most 4⌈log₂n⌉.

14.4 Usage Example

# Create segment tree
nums = [1, 3, 5, 7, 9, 11]
st = SegmentTree(nums)

# Query sum of [1, 4]: 3 + 5 + 7 + 9 = 24
print(st.query(1, 4))  # Output: 24

# Update nums[2] to 10
st.update(2, 10)

# Query [1, 4] again: 3 + 10 + 7 + 9 = 29
print(st.query(1, 4))  # Output: 29

14.5 Binary Indexed Tree (BIT / Fenwick Tree)

A Binary Indexed Tree is another data structure for prefix sum queries with point updates. It is more concise than a segment tree with smaller constants, but has more limited functionality (the basic version only supports prefix queries, not arbitrary range max/min).

Core Idea: A BIT uses the lowest set bit (lowbit) of binary representation to partition the original array into "responsibility intervals" of varying lengths. Position i is responsible for storing the aggregate of elements from i - lowbit(i) + 1 to i.

The lowbit operation: lowbit(x) = x & (-x) extracts the lowest set bit of x.

x = 12 = 1100₂
-x = ...10100₂ (two's complement)
x & (-x) = 00100₂ = 4
So lowbit(12) = 4, meaning position 12 manages a segment of 4 elements: [9, 12]

Why does lowbit work? This is not coincidental but carefully designed. Peter Fenwick showed in his 1994 paper that if we manage the array in layers according to lowbit:

• Updating position i requires updating positions i, i + lowbit(i), i + lowbit(next), ...—each step the lowbit increases, so at most O(log n) steps
• Querying prefix sum [1..i] requires accumulating positions i, i - lowbit(i), i - lowbit(next), ...—each step removes the lowest set bit, at most O(log n) steps

class BinaryIndexedTree:
    """Binary Indexed Tree — supports point update and prefix sum query"""
    
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed
    
    @staticmethod
    def lowbit(x):
        return x & (-x)
    
    def update(self, i, delta):
        """Add delta to position i (1-indexed)"""
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)
    
    def prefix_sum(self, i):
        """Query prefix sum [1..i] (1-indexed)"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= self.lowbit(i)
        return s
    
    def range_sum(self, l, r):
        """Query range sum [l..r] (1-indexed)"""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Building a BIT from an existing array:

def build_from_array(nums):
    """O(n log n) construction"""
    n = len(nums)
    bit = BinaryIndexedTree(n)
    for i, val in enumerate(nums):
        bit.update(i + 1, val)
    return bit

def build_from_array_linear(nums):
    """O(n) construction — exploiting parent-child relationships"""
    n = len(nums)
    bit = BinaryIndexedTree(n)
    for i in range(1, n + 1):
        bit.tree[i] += nums[i - 1]
        parent = i + (i & (-i))
        if parent <= n:
            bit.tree[parent] += bit.tree[i]
    return bit

14.6 Segment Tree vs. BIT: When to Use Which

Rules of Thumb:

• Need only prefix sums + point updates → use BIT
• Need range min/max or range update + range query → use segment tree
• Want shortest possible code → use BIT
• Need persistence or dynamic allocation → segment tree only

14.7 Common Errors and Debugging

Error 1: Insufficient array space

# Wrong: allocating 2n
self.tree = [0] * (2 * self.n)  # Overflows when n is not a power of 2!

# Correct: allocate 4n
self.tree = [0] * (4 * self.n)

Error 2: Using 0-indexed BIT

# Wrong: starting i from 0; lowbit(0) = 0 causes infinite loop!
def update(self, i, delta):
    while i <= self.n:
        self.tree[i] += delta
        i += self.lowbit(i)  # If i=0, lowbit(0)=0, never increments

# Correct: BIT must be 1-indexed

Error 3: Missing no-intersection check in query

# Wrong: no intersection check
def _query(self, node, start, end, l, r):
    if l <= start and end <= r:
        return self.tree[node]
    mid = (start + end) // 2
    return self._query(2*node, start, mid, l, r) + \
           self._query(2*node+1, mid+1, end, l, r)

# Correct: add no-intersection check
def _query(self, node, start, end, l, r):
    if l <= start and end <= r:
        return self.tree[node]
    if end < l or start > r:
        return 0  # Identity element for no intersection
    mid = (start + end) // 2
    return self._query(2*node, start, mid, l, r) + \
           self._query(2*node+1, mid+1, end, l, r)

Error 4: Forgetting to update parent after update

# Wrong
def _update(self, node, start, end, idx, val):
    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)
    # Forgetting this line breaks everything!
    # self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

Level 2 · How It Works Internally

14.8 Lazy Propagation

The basic segment tree only supports point updates. But if you need range updates (add a value to all elements in nums[l..r]), the naive approach of updating r - l + 1 individual points degrades to O(n log n).

Lazy Propagation's core idea is deferred updates: when a range update completely covers a node's interval, don't push the update down to children immediately. Instead, mark the node with a "lazy tag" indicating "this node's subtree has pending propagation." Only when a subsequent operation needs to access children do we push the lazy tag down (pushdown).

Why is this correct? Because if subsequent operations never access the children, their exact values are never needed. Computing them on demand is the essence of "lazy evaluation"—a concept also found in functional programming.

class SegmentTreeLazy:
    """Segment Tree with Lazy Propagation — range update + range query"""
    
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)  # Lazy tag array
        if self.n > 0:
            self._build(nums, 1, 0, self.n - 1)
    
    def _build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return
        mid = (start + end) // 2
        self._build(nums, 2 * node, start, mid)
        self._build(nums, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def _pushdown(self, node, start, end):
        """Push lazy tag down to children"""
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            left_len = mid - start + 1
            right_len = end - mid
            
            # Update left child's value and lazy tag
            self.tree[2 * node] += self.lazy[node] * left_len
            self.lazy[2 * node] += self.lazy[node]
            
            # Update right child's value and lazy tag
            self.tree[2 * node + 1] += self.lazy[node] * right_len
            self.lazy[2 * node + 1] += self.lazy[node]
            
            # Clear current node's lazy tag
            self.lazy[node] = 0
    
    def range_update(self, l, r, val):
        """Range update: add val to all elements in nums[l..r]"""
        self._range_update(1, 0, self.n - 1, l, r, val)
    
    def _range_update(self, node, start, end, l, r, val):
        # Fully covered — set lazy tag, don't push down
        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return
        # No intersection
        if end < l or start > r:
            return
        # Partial overlap — push down existing lazy, then recurse
        self._pushdown(node, start, end)
        mid = (start + end) // 2
        self._range_update(2 * node, start, mid, l, r, val)
        self._range_update(2 * node + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def range_query(self, l, r):
        """Range query: compute sum of nums[l..r]"""
        return self._range_query(1, 0, self.n - 1, l, r)
    
    def _range_query(self, node, start, end, l, r):
        if l <= start and end <= r:
            return self.tree[node]
        if end < l or start > r:
            return 0
        # Critical: must push down before accessing children
        self._pushdown(node, start, end)
        mid = (start + end) // 2
        return self._range_query(2 * node, start, mid, l, r) + \
               self._range_query(2 * node + 1, mid + 1, end, l, r)

Complexity Analysis of Lazy Propagation:

Both range update and range query remain O(log n). The proof is similar to point update—each level has at most a constant number of "partially covered" nodes, and pushdown itself is O(1).

Correctness Condition for Lazy Propagation:

Lazy tags must satisfy composability: multiple accumulated lazy tags can be correctly merged. For "range add," lazy tags simply accumulate; for "range assign," a new tag overwrites the old one. When both "range add" and "range multiply" exist simultaneously, tag design becomes more complex (maintaining a (multiplier, addend) pair with careful ordering during pushdown).

14.9 Lazy Propagation Usage Example

# Scenario: frequent range adds and range sum queries
nums = [1, 3, 5, 7, 9, 11]
st = SegmentTreeLazy(nums)

# Add 3 to all elements in [1, 4]: [1, 6, 8, 10, 12, 11]
st.range_update(1, 4, 3)

# Query sum of [2, 5]: 8 + 10 + 12 + 11 = 41
print(st.range_query(2, 5))  # Output: 41

# Add -1 to all elements in [0, 2]: [0, 5, 7, 10, 12, 11]
st.range_update(0, 2, -1)

# Query sum of [0, 5]: 0 + 5 + 7 + 10 + 12 + 11 = 45
print(st.range_query(0, 5))  # Output: 45

14.10 Dynamic Node Allocation for Segment Trees

Standard segment trees use an array for storage, requiring pre-allocation of 4n space. But if the value domain is huge (e.g., [0, 10^9]), you cannot allocate an array of size 4×10^9. Dynamic node allocation creates nodes only when needed.

class DynamicSegTree:
    """Dynamic Segment Tree — supports large value domains"""
    
    def __init__(self):
        self.tree = {}   # node_id -> value
        self.lazy = {}   # node_id -> lazy_value
        self.left_child = {}   # node_id -> left_child_id
        self.right_child = {}  # node_id -> right_child_id
        self.cnt = 0     # Node counter
        self.root = self._new_node()
    
    def _new_node(self):
        self.cnt += 1
        self.tree[self.cnt] = 0
        self.lazy[self.cnt] = 0
        return self.cnt
    
    def _pushdown(self, node, left_len, right_len):
        if self.lazy.get(node, 0) == 0:
            return
        # Ensure children exist
        if node not in self.left_child:
            self.left_child[node] = self._new_node()
        if node not in self.right_child:
            self.right_child[node] = self._new_node()
        
        lc, rc = self.left_child[node], self.right_child[node]
        self.tree[lc] += self.lazy[node] * left_len
        self.lazy[lc] = self.lazy.get(lc, 0) + self.lazy[node]
        self.tree[rc] += self.lazy[node] * right_len
        self.lazy[rc] = self.lazy.get(rc, 0) + self.lazy[node]
        self.lazy[node] = 0
    
    def update(self, node, start, end, l, r, val):
        """Add val to interval [l, r]"""
        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] = self.lazy.get(node, 0) + val
            return
        mid = (start + end) // 2
        self._pushdown(node, mid - start + 1, end - mid)
        if node not in self.left_child:
            self.left_child[node] = self._new_node()
        if node not in self.right_child:
            self.right_child[node] = self._new_node()
        if l <= mid:
            self.update(self.left_child[node], start, mid, l, r, val)
        if r > mid:
            self.update(self.right_child[node], mid + 1, end, l, r, val)
        self.tree[node] = self.tree[self.left_child[node]] + \
                          self.tree[self.right_child[node]]
    
    def query(self, node, start, end, l, r):
        """Query sum of interval [l, r]"""
        if l <= start and end <= r:
            return self.tree.get(node, 0)
        if end < l or start > r:
            return 0
        mid = (start + end) // 2
        self._pushdown(node, mid - start + 1, end - mid)
        res = 0
        if l <= mid and node in self.left_child:
            res += self.query(self.left_child[node], start, mid, l, r)
        if r > mid and node in self.right_child:
            res += self.query(self.right_child[node], mid + 1, end, l, r)
        return res

Space Complexity of Dynamic Allocation: Each update creates at most O(log n) new nodes (the root-to-leaf path). With q operations, total space is O(q log n).

Typical Use Cases:

• Large value domain but limited operations (e.g., coordinates in [0, 10^9] but only 10^5 operations)
• Persistent segment trees (creating new nodes per modification without altering old ones)

14.11 Counting Inversions with BIT

Inversion Problem: Given array nums, count pairs (i, j) where i < j and nums[i] > nums[j].

This is a classic BIT application. The approach: traverse the array from right to left. For each element nums[i], query "how many elements already encountered are smaller than nums[i]"—this is the inversion count involving nums[i].

def count_inversions(nums):
    """Count inversions using BIT"""
    if not nums:
        return 0
    
    # Coordinate compression: map values to [1, n]
    sorted_unique = sorted(set(nums))
    rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
    
    n = len(sorted_unique)
    bit = BinaryIndexedTree(n)
    inversions = 0
    
    # Traverse right to left
    for i in range(len(nums) - 1, -1, -1):
        r = rank[nums[i]]
        # Query count of elements smaller than nums[i] (already in BIT)
        inversions += bit.prefix_sum(r - 1)
        # Insert nums[i] into BIT
        bit.update(r, 1)
    
    return inversions

# Example
print(count_inversions([2, 4, 1, 3, 5]))  # Output: 3
# Inversions: (2,1), (4,1), (4,3)

Time Complexity: O(n log n) — coordinate compression O(n log n) + each BIT operation O(log n) during traversal.

14.12 Two-Dimensional BIT

A 2D BIT handles "point update + rectangular region sum query" on a matrix.

class BIT2D:
    """Two-dimensional Binary Indexed Tree"""
    
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
    
    def update(self, x, y, delta):
        """Add delta to position (x, y) (1-indexed)"""
        i = x
        while i <= self.rows:
            j = y
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
    
    def prefix_sum(self, x, y):
        """Query rectangular sum from (1,1) to (x,y)"""
        s = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s
    
    def range_sum(self, x1, y1, x2, y2):
        """Query rectangular sum from (x1,y1) to (x2,y2) using inclusion-exclusion"""
        return (self.prefix_sum(x2, y2)
                - self.prefix_sum(x1 - 1, y2)
                - self.prefix_sum(x2, y1 - 1)
                + self.prefix_sum(x1 - 1, y1 - 1))

Complexity of 2D BIT: Each update/query is O(log m × log n); space is O(m × n).

Comparison with 2D Prefix Sums:

• If the matrix never changes, 2D prefix sums suffice (O(1) query)
• If the matrix needs updates, use 2D BIT (O(log² n) for both query and update)

14.13 Internal Execution Model

Understanding these data structures requires understanding how they "decompose" intervals.

Segment Tree Interval Decomposition:

For n=8, querying [2, 7]:

               [0,7]
           /          \
       [0,3]          [4,7]
      /     \        /     \
   [0,1]  [2,3]  [4,5]  [6,7]
   / \    / \    / \    / \
 [0][1] [2][3] [4][5] [6][7]

Query [2,7]:
- [0,7] partial overlap, recurse
  - [0,3] partial overlap, recurse
    - [0,1] no intersection, return 0
    - [2,3] fully contained, return tree[[2,3]]  ✓
  - [4,7] fully contained, return tree[[4,7]]  ✓

Result = tree[[2,3]] + tree[[4,7]]
Only 2 node values cover the entire [2,7] range!

BIT Prefix Decomposition:

Querying prefix_sum(7) (1-indexed):

i = 7 = 111₂, tree[7] covers [7,7] (lowbit=1)
i -= 1 → i = 6 = 110₂, tree[6] covers [5,6] (lowbit=2)
i -= 2 → i = 4 = 100₂, tree[4] covers [1,4] (lowbit=4)
i -= 4 → i = 0, done

prefix_sum(7) = tree[7] + tree[6] + tree[4]
             = [7,7] + [5,6] + [1,4]
             = [1,7]  ✓

The mathematical essence: stripping bits from the binary representation of i one by one. The number of set bits in i determines how many tree values need to be summed. At most ⌊log₂n⌋ + 1.

14.14 More Variants: Range Update + Point Query (Difference BIT)

If you need "range update" but only "point query," build a BIT on the difference array:

class DiffBIT:
    """Difference BIT: range update + point query"""
    
    def __init__(self, n):
        self.bit = BinaryIndexedTree(n)
    
    def range_add(self, l, r, val):
        """Add val to all elements in [l, r] (1-indexed)"""
        self.bit.update(l, val)
        if r + 1 <= self.bit.n:
            self.bit.update(r + 1, -val)
    
    def point_query(self, i):
        """Query current value at position i"""
        return self.bit.prefix_sum(i)

Principle: Build a BIT on the difference array d. range_add(l, r, val) is equivalent to d[l] += val, d[r+1] -= val. Then point_query(i) = prefix_sum(d, i) = cumulative increment at position i.

For "range update + range query," use two BITs together:

class RangeAddRangeSum:
    """Two BITs for range add + range sum"""
    
    def __init__(self, nums):
        self.n = len(nums)
        self.bit1 = BinaryIndexedTree(self.n)  # Stores d[i]
        self.bit2 = BinaryIndexedTree(self.n)  # Stores i * d[i]
        # Original prefix sums
        self.prefix = [0] * (self.n + 1)
        for i in range(self.n):
            self.prefix[i + 1] = self.prefix[i] + nums[i]
    
    def range_add(self, l, r, val):
        """Add val to interval [l, r] (1-indexed)"""
        self.bit1.update(l, val)
        self.bit1.update(r + 1, -val)
        self.bit2.update(l, val * l)
        self.bit2.update(r + 1, -val * (r + 1))
    
    def prefix_sum(self, i):
        """Query prefix sum [1..i]"""
        return self.prefix[i] + \
               (i + 1) * self.bit1.prefix_sum(i) - \
               self.bit2.prefix_sum(i)
    
    def range_sum(self, l, r):
        """Query range sum [l, r]"""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Derivation: Let the original array be a, difference array be d (d[i] = a[i] - a[i-1]).

The prefix sum a[1] + a[2] + ... + a[i] expands to:

Σ(k=1 to i) a[k] = Σ(k=1 to i) Σ(j=1 to k) d[j]
                  = Σ(j=1 to i) d[j] * (i - j + 1)
                  = (i+1) * Σ(j=1 to i) d[j] - Σ(j=1 to i) j * d[j]

So we only need two prefix sums: Σd[j] and Σj*d[j], each maintained by a BIT.

Level 3 · What the Specifications Say

14.15 Peter Fenwick's Original Paper (1994)

The Binary Indexed Tree was formally introduced by Peter Fenwick in his 1994 paper "A New Data Structure for Cumulative Frequency Tables" (Software: Practice and Experience, Vol. 24(3), pp. 327-336, March 1994).

Background: Fenwick's original motivation was arithmetic coding and cumulative frequency tables used in data compression. Two operations were needed frequently:

1. Update a symbol's frequency (point update)
2. Query the cumulative frequency of all symbols up to a threshold (prefix sum query)

The traditional approach maintained a flat cumulative table with O(n) updates; balanced trees worked but were complex to implement. Fenwick proposed an elegant method using binary representation of integers, achieving O(log n) for both operations with remarkably concise code.

Key Design Decision:

Fenwick explained in the paper why "removing the lowest set bit" is the core operation:

"The key observation is that any positive integer can be uniquely represented as a sum of distinct powers of 2. The tree structure exploits this by assigning responsibility for cumulative frequencies in a manner that mirrors binary representation."

Any positive integer i can be uniquely decomposed into a sum of powers of 2. The BIT structure exploits this—position i manages lowbit(i) consecutive elements, and traversing from position i by repeatedly subtracting lowbit(i) decomposes [1, i] into O(log i) non-overlapping segments.

Fenwick's Core Theorem:

Theorem: For any positive integer i, the sequence obtained by repeatedly applying i -= lowbit(i) starting from i, yielding i₁, i₂, ..., iₖ, satisfies:

1. The sequence is strictly decreasing, terminating at 0
2. The intervals [iⱼ - lowbit(iⱼ) + 1, iⱼ] (j = 1, ..., k) are pairwise disjoint
3. Their union is exactly [1, i]
4. k ≤ ⌊log₂i⌋ + 1

Proof Sketch: Each subtraction of lowbit(i) removes the lowest set bit from i's binary representation. If i has k set bits, exactly k steps reach 0. Each step's interval length equals the removed power of 2. Since binary decomposition is unique, these intervals are disjoint and cover [1, i].

14.16 History of Segment Trees

The segment tree has a longer history than the BIT, but its development was not defined by a single paper—it was gradually refined by multiple researchers in computational geometry and algorithms.

1977 — Jon Bentley: In "Solutions to Klee's Rectangle Problems" (Carnegie-Mellon University, 1977), Bentley described a tree structure based on interval partitioning for solving the rectangle union area problem (Klee's Rectangle Problem). This is one of the earliest sources of segment tree ideas.

1979 — Bentley and Wood: "An Optimal Worst-Case Algorithm for Reporting Intersections of Rectangles" (IEEE Transactions on Computers, 1980) further developed the theoretical foundation of interval trees.

1980s — McCreight, Willard, and others: Segment trees evolved into a general-purpose interval management structure, widely used in computational geometry (segment intersection, window queries, etc.).

Important Clarification: In academic literature, "Segment Tree" typically refers to a specific interval storage structure (each interval is decomposed and stored in O(log n) nodes), which has subtle differences from the "segment tree" in competitive programming (essentially a statistic tree or recursive interval aggregation tree). However, in the modern algorithms community, "Segment Tree" has become the conventional term for the competitive programming structure.

14.17 Persistent Segment Tree (Chairman Tree)

A Persistent Segment Tree can preserve all historical versions of a segment tree across modifications. It was popularized in the Chinese competitive programming community by Huang Jiatai (online handle "Chairman"), hence called "Chairman Tree" (主席树) in Chinese.

Core Idea: Instead of modifying existing nodes during an update, create new nodes. Since each update only affects one root-to-leaf path (O(log n) nodes), only O(log n) new nodes are created per version; all other nodes are shared with the previous version.

class PersistentSegTree:
    """Persistent Segment Tree — creates new version per modification"""
    
    def __init__(self, max_nodes=2000000):
        self.lc = [0] * max_nodes   # Left child id
        self.rc = [0] * max_nodes   # Right child id
        self.val = [0] * max_nodes  # Node value
        self.cnt = 0                # Current node count
        self.roots = []             # Root node id for each version
    
    def _new_node(self):
        self.cnt += 1
        return self.cnt
    
    def build(self, start, end):
        """Build initial version"""
        node = self._new_node()
        if start == end:
            return node
        mid = (start + end) // 2
        self.lc[node] = self.build(start, mid)
        self.rc[node] = self.build(mid + 1, end)
        return node
    
    def update(self, prev, start, end, pos, delta):
        """Create new version based on prev, adding delta at pos"""
        node = self._new_node()
        self.lc[node] = self.lc[prev]
        self.rc[node] = self.rc[prev]
        self.val[node] = self.val[prev] + delta
        if start == end:
            return node
        mid = (start + end) // 2
        if pos <= mid:
            self.lc[node] = self.update(self.lc[prev], start, mid, pos, delta)
        else:
            self.rc[node] = self.update(self.rc[prev], mid + 1, end, pos, delta)
        return node
    
    def query(self, left_root, right_root, start, end, k):
        """Query k-th smallest between two versions"""
        if start == end:
            return start
        mid = (start + end) // 2
        left_count = self.val[self.lc[right_root]] - self.val[self.lc[left_root]]
        if k <= left_count:
            return self.query(self.lc[left_root], self.lc[right_root],
                            start, mid, k)
        else:
            return self.query(self.rc[left_root], self.rc[right_root],
                            mid + 1, end, k - left_count)

Classic Application: K-th Smallest in a Range

Given an array, query the k-th smallest element in any range [l, r].

Approach:

1. Build a segment tree over the value domain; each leaf represents a value
2. Insert elements sequentially—version i represents the tree with the first i elements
3. Query k-th smallest in [l, r] = subtract version l-1 from version r to get the frequency distribution in [l, r], then binary search

Space Complexity: Initial version has O(n) nodes; each modification adds O(log n) new nodes. After n modifications, total space is O(n log n).

14.18 Segment Trees in Competitive Programming

Segment trees are one of the most central data structures in competitive programming (ACM-ICPC, Codeforces, AtCoder, NOI/IOI). According to Codeforces problem tag statistics, problems tagged "segment tree" or "data structures" account for over 20% of all problems, especially concentrated at Div. 1 level (rating 1900+).

Why are segment trees so important? Because they offer exceptional generality and extensibility:

1. Generality: Any information satisfying "interval mergeability" can be maintained by a segment tree—range sums, range min/max, range GCD, range matrix products, range hash values, etc.

2. Extensibility:

   • Add lazy propagation → supports range updates
   • Add persistence → supports historical version queries
   • Add dynamic allocation → supports large value domains
   • Segment tree merging → solves tree-based problems
   • Li Chao tree → maintains convex hull / line collections
   • Segment tree binary search → eliminates need for external binary search

Codeforces Rating vs. Segment Tree Frequency:

Level 4 · Edge Cases and Pitfalls

14.19 Interview Problem: Range Sum Query — Mutable (LeetCode #307)

Problem: Implement the NumArray class:

• NumArray(nums) — initializes with array nums
• update(index, val) — sets nums[index] to val
• sumRange(left, right) — returns sum of nums[left..right]

Analysis: This is the most fundamental segment tree/BIT application. Both work, but BIT produces shorter code.

class NumArray:
    """Solution 1: Binary Indexed Tree"""
    
    def __init__(self, nums):
        self.n = len(nums)
        self.nums = nums[:]
        self.bit = [0] * (self.n + 1)
        for i in range(self.n):
            self._add(i + 1, nums[i])
    
    def _add(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)
    
    def _prefix(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)
        return s
    
    def update(self, index, val):
        delta = val - self.nums[index]
        self.nums[index] = val
        self._add(index + 1, delta)
    
    def sumRange(self, left, right):
        return self._prefix(right + 1) - self._prefix(left)

class NumArray2:
    """Solution 2: Segment Tree"""
    
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(nums, 1, 0, self.n - 1)
    
    def _build(self, nums, node, s, e):
        if s == e:
            self.tree[node] = nums[s]
            return
        mid = (s + e) // 2
        self._build(nums, 2*node, s, mid)
        self._build(nums, 2*node+1, mid+1, e)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def update(self, index, val):
        self._update(1, 0, self.n-1, index, val)
    
    def _update(self, node, s, e, idx, val):
        if s == e:
            self.tree[node] = val
            return
        mid = (s + e) // 2
        if idx <= mid:
            self._update(2*node, s, mid, idx, val)
        else:
            self._update(2*node+1, mid+1, e, idx, val)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def sumRange(self, left, right):
        return self._query(1, 0, self.n-1, left, right)
    
    def _query(self, node, s, e, l, r):
        if l <= s and e <= r:
            return self.tree[node]
        if e < l or s > r:
            return 0
        mid = (s + e) // 2
        return self._query(2*node, s, mid, l, r) + \
               self._query(2*node+1, mid+1, e, l, r)

Interview Key Points:

• Be able to write both solutions
• Explain why prefix sums don't work (O(n) update cost)
• BIT solution: note that update must compute the delta val - nums[index]
• Time complexity: build O(n log n), each operation O(log n)

14.20 Interview Problem: Count of Smaller Numbers After Self (LeetCode #315)

Problem: Given array nums, return array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller.

Analysis: This is essentially an "inversion" variant—for each position i, count the inversions it forms with elements to its right.

def countSmaller(nums):
    """Traverse right to left, count with BIT"""
    if not nums:
        return []
    
    # Coordinate compression
    sorted_unique = sorted(set(nums))
    rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
    
    n = len(sorted_unique)
    bit = [0] * (n + 1)
    
    def update(i):
        while i <= n:
            bit[i] += 1
            i += i & (-i)
    
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    result = []
    for i in range(len(nums) - 1, -1, -1):
        r = rank[nums[i]]
        # Query count of elements in BIT smaller than nums[i]
        result.append(query(r - 1))
        update(r)
    
    return result[::-1]

# Example
print(countSmaller([5, 2, 6, 1]))  # [2, 1, 1, 0]

Alternative: Segment Tree Solution

def countSmaller_segtree(nums):
    """Use segment tree to count smaller elements to the right"""
    if not nums:
        return []
    
    # Coordinate compression
    sorted_unique = sorted(set(nums))
    rank = {v: i for i, v in enumerate(sorted_unique)}
    m = len(sorted_unique)
    
    # Segment tree maintains count of each value
    tree = [0] * (4 * m)
    
    def update(node, s, e, idx):
        if s == e:
            tree[node] += 1
            return
        mid = (s + e) // 2
        if idx <= mid:
            update(2*node, s, mid, idx)
        else:
            update(2*node+1, mid+1, e, idx)
        tree[node] = tree[2*node] + tree[2*node+1]
    
    def query(node, s, e, l, r):
        if l > r:
            return 0
        if l <= s and e <= r:
            return tree[node]
        if e < l or s > r:
            return 0
        mid = (s + e) // 2
        return query(2*node, s, mid, l, r) + query(2*node+1, mid+1, e, l, r)
    
    result = []
    for i in range(len(nums) - 1, -1, -1):
        r = rank[nums[i]]
        # Query count of elements in range [0, r-1]
        result.append(query(1, 0, m-1, 0, r-1))
        update(1, 0, m-1, r)
    
    return result[::-1]

Interview Extensions:

• This problem can also be solved with merge sort (counting inversions during merge)
• BIT solution has the shortest code—recommended for interviews
• Coordinate compression is the key step; interviewers may ask why it's needed (BIT indices must be positive integers and not too large)

14.21 Common Segment Tree Implementation Errors

In contests and interviews, segment tree implementations have many subtle error sources. Here are the Top 10 errors ranked by severity:

1. Insufficient space allocation

# Wrong: n=5 requires more space than 2*5
tree = [0] * (2 * n)  # Not enough!

# Correct
tree = [0] * (4 * n)

Why? When n=5, height h = ⌈log₂5⌉ = 3, full binary tree nodes = 2^4 - 1 = 15, so we need 16 (1-indexed). 2n = 10 is clearly insufficient.

2. Missing pushdown in lazy propagation

# Wrong: no pushdown before recursing in update
def _range_update(self, node, start, end, l, r, val):
    if l <= start and end <= r:
        self.tree[node] += val * (end - start + 1)
        self.lazy[node] += val
        return
    # Forgot pushdown! Children may have unprocessed old lazy values
    mid = (start + end) // 2
    self._range_update(2*node, start, mid, l, r, val)
    ...

3. Wrong interval length in pushdown

# Wrong
left_len = mid - start  # Off by one!
right_len = end - mid - 1  # Off by one!

# Correct
left_len = mid - start + 1
right_len = end - mid

4. Wrong leaf node condition

# Wrong: using node >= n as leaf check
if node >= self.n:  # Wrong for array-based segment trees

# Correct: use start == end
if start == end:
    ...

5. Wrong identity element for range query

# For range minimum query
if end < l or start > r:
    return 0  # Wrong! Should return infinity

# Correct
if end < l or start > r:
    return float('inf')  # Identity for minimum query

Identity elements for different operations: sum → 0, min → +∞, max → -∞, GCD → 0, product → 1.

6. Confusing "set to" vs "add to" in update

# "Set to val" version
def _update(self, node, start, end, idx, val):
    if start == end:
        self.tree[node] = val  # Direct assignment
        return
    ...

# "Add delta" version
def _update(self, node, start, end, idx, delta):
    if start == end:
        self.tree[node] += delta  # Accumulate
        return
    ...

Always clarify with the interviewer whether the problem requires "set" or "add."

7. BIT 0-indexing infinite loop

# If i=0 is passed, lowbit(0)=0, both update and query loop forever
# BIT must start from 1!

8. Forgetting to use rank after coordinate compression

# Wrong
bit.update(nums[i], 1)  # nums[i] could be 10^9, can't allocate that!

# Correct
bit.update(rank[nums[i]], 1)  # rank is in [1, n]

9. Missing null node handling in segment tree merging

# Wrong
def merge(a, b, s, e):
    new_node = ...
    new_node.left = merge(a.left, b.left, ...)
    new_node.right = merge(a.right, b.right, ...)
    # Crashes if a or b is None

# Correct
def merge(a, b, s, e):
    if a is None: return b
    if b is None: return a
    ...

10. Priority issues with multiple lazy operations

When both "range assign" and "range add" coexist, pushdown order is critical:

# If assign first, then add: child = assigned_value + later_addition
# If add first, then assign: child = assigned_value (addition overwritten)
# Must track operation timestamps, or unify as (multiply, add) pairs

14.22 When to Use Prefix Sums vs. Segment Trees

This is the most commonly asked "choice" question in interviews.

Interview Answer Template:

"First I analyze the operation types: if the array is static (no modifications), prefix sums suffice with O(1) queries. If modifications are needed, I check whether they're point or range. Point updates + range sums → BIT is simplest. Range updates or maintaining min/max → segment tree with lazy propagation. Specifically for this problem..."

14.23 Advanced Technique: Binary Search on Segment Tree

A powerful feature of segment trees is performing binary search directly on the tree structure, avoiding an extra O(log n) factor.

Example: "Find the leftmost position i such that prefix_sum(0, i) >= target."

Naive approach: external binary search + segment tree query → O(log² n)

Binary search on segment tree: O(log n)

def find_first(self, target):
    """Find minimum i such that prefix[0..i] >= target"""
    return self._find_first(1, 0, self.n - 1, target)

def _find_first(self, node, start, end, target):
    if start == end:
        return start if self.tree[node] >= target else -1
    mid = (start + end) // 2
    # If left subtree sum >= target, answer is in left subtree
    if self.tree[2 * node] >= target:
        return self._find_first(2 * node, start, mid, target)
    else:
        # Otherwise answer is in right subtree, subtract left contribution
        return self._find_first(2 * node + 1, mid + 1, end,
                               target - self.tree[2 * node])

Why is this faster than "external binary search + query"? External binary search needs O(log n) queries, each O(log n), totaling O(log² n). Binary search on the segment tree traverses only one root-to-leaf path: O(log n). In time-critical contest problems, this can be the difference between AC and TLE.

14.24 Practical Experience Summary

Competitive Programming Segment Tree Checklist:

1. Determine the identity element: Before coding, decide what your query returns for no intersection (sum→0, min→INF, max→-INF, GCD→0, XOR→0)

2. Determine the merge function: How internal nodes compute their value from children. For complex information (e.g., maximum subarray sum), the merge function may need multiple fields (prefix max sum, suffix max sum, total sum, max subarray sum)

3. Lazy tag design:

   • What is the initial value ("no tag" state)?
   • How do two tags merge?
   • How does a tag apply to a node's value?
   • Get these three questions right, and the code won't have bugs

4. Testing recommendations:

   • Stress test against brute-force O(n) solution
   • Specifically test n=1, n=2 edge cases
   • Test with operation interval = full array
   • Test with operation interval = single point

# Stress test template
import random

def stress_test(n=100, q=1000, max_val=100):
    """Brute-force comparison to verify segment tree correctness"""
    nums = [random.randint(0, max_val) for _ in range(n)]
    st = SegmentTree(nums[:])
    
    for _ in range(q):
        op = random.randint(0, 1)
        if op == 0:  # update
            idx = random.randint(0, n-1)
            val = random.randint(0, max_val)
            nums[idx] = val
            st.update(idx, val)
        else:  # query
            l = random.randint(0, n-1)
            r = random.randint(l, n-1)
            expected = sum(nums[l:r+1])
            got = st.query(l, r)
            assert expected == got, f"Mismatch at [{l},{r}]: expected {expected}, got {got}"
    
    print("All tests passed!")

stress_test()

Segment Tree Thinking for Interviews:

When interviewers ask segment tree questions, they usually don't expect perfect code (too long), but test your thinking process:

1. Can you identify this as a "range query + update" problem?
2. Can you select the appropriate data structure (prefix sums / BIT / segment tree)?
3. Can you analyze time and space complexity?
4. Can you write complete BIT code?
5. Can you clearly describe the build, query, and update processes for segment trees?

You don't need to write a full lazy-propagation segment tree on a whiteboard—that's for competitive programmers in IDEs. But basic segment tree and BIT code should be writable within 10 minutes.

14.25 Further Reading and Practice

Must-Practice Problems:

Advanced Problems (Codeforces):

Recommended Resources:

1. Peter Fenwick, "A New Data Structure for Cumulative Frequency Tables", Software: Practice and Experience, 1994
2. Thomas H. Cormen et al., "Introduction to Algorithms" (CLRS), Chapter 14 (Augmenting Data Structures)
3. Competitive Programmer's Handbook (Antti Laaksonen), Chapter 9: Range Queries
4. CP-Algorithms (cp-algorithms.com) — Segment Tree section (extensive variants and code templates)