Module 12: Segment Tree & Fenwick Tree (Binary Indexed Tree)

Goal: Master Segment Trees (with Lazy Propagation) and Fenwick Trees from absolute zero — understand the why, how, and when of each structure so you can confidently solve any range-query problem in a DSA interview.
Language: C++ (C++17)
Prerequisites: Arrays, Recursion, Binary Trees (Module 06)

📑 Table of Contents

The Problem They Solve — Motivation
Segment Tree — From Scratch
- 2.1 Mental Model & Visual Intuition
- 2.2 Building the Tree — Step by Step
- 2.3 Range Query — Step by Step
- 2.4 Point Update — Step by Step
- 2.5 Full C++ Implementation
- 2.6 Lazy Propagation
Fenwick Tree (BIT) — From Scratch
- 3.1 Mental Model — The Magic of i & (-i)
- 3.2 Building the Tree
- 3.3 Prefix Sum Query
- 3.4 Point Update
- 3.5 Full C++ Implementation
- 3.6 Range Update + Range Query (Advanced BIT)
Segment Tree vs Fenwick Tree — Decision Guide
Common Variants & Extensions
10 Practice Problems with Full Solutions
Interview Cheat Sheet

1. The Problem They Solve — Motivation

The Naive Approach and Why It Fails

Suppose you have an array a of N integers and you receive Q queries:

Range Sum Query: What is a[l] + a[l+1] + ... + a[r]?
Point Update: Set a[i] = v.

Option 1: Brute Force

Query:  O(N) per query  →  Q queries = O(N·Q)  catastrophic for N=Q=10^5 (10^10 ops)
Update: O(1)

Option 2: Prefix Sum Array

Build:  O(N)
Query:  O(1)   great!
Update: O(N)   terrible! Must rebuild entire prefix array after each update.

Neither option handles both queries and updates efficiently at the same time.

The Goal

Structure	Build	Point Update	Range Query	Range Update	Range Query (after range update)
Brute Force	O(1)	O(1)	O(N)	O(N)	O(N)
Prefix Sum	O(N)	O(N)	O(1)	O(N)	O(1)
Fenwick Tree	O(N logN)	O(log N)	O(log N)	O(log N)*	O(log N)*
Segment Tree	O(N)	O(log N)	O(log N)	O(log N)	O(log N)

Both achieve O(log N) per operation — a sweet spot between the two extremes.

2. Segment Tree — From Scratch

2.1 Mental Model & Visual Intuition

A Segment Tree is a binary tree where:

Each leaf represents a single element of the array.
Each internal node represents a segment (range) of the array and stores a combined result (e.g., sum, min, max) of that range.

Example: Array a = [1, 3, 5, 7, 9, 11]

Index:           0  1  2  3  4  5
Array:           1  3  5  7  9  11

                  [sum[0..5] = 36]           <-- root covers entire array
                  /                \
      [sum[0..2] = 9]         [sum[3..5] = 27]
          /        \               /          \
  [sum[0..1]=4] [sum[2..2]=5] [sum[3..4]=16] [sum[5..5]=11]
      /     \                     /      \
  [a[0]=1] [a[1]=3]           [a[3]=7] [a[4]=9]

Key Insight: Every query range [l, r] can be broken down into O(log N) pre-computed segments.

Array Representation of the Tree

Just like a Binary Heap, we store the segment tree in a 1-indexed flat array of size 4*N:

tree[1]  = root  (covers [0, N-1])
tree[2]  = left child of root  (covers [0, mid])
tree[3]  = right child of root (covers [mid+1, N-1])

Parent of node i  → i / 2
Left child of i   → 2 * i
Right child of i  → 2 * i + 1

Why 4*N? At most 2 * 2^(ceil(log2(N))) nodes. 4*N is a safe upper bound for any N.

2.2 Building the Tree — Step by Step

Idea: Recursively split the range in half. Leaf nodes store the actual values. Internal nodes store the aggregate of their two children.

build(node, start, end, arr):
    if start == end:           <- LEAF: store actual value
        tree[node] = arr[start]
        return
    mid = (start + end) / 2
    build(2*node,   start, mid, arr)       <- build left child
    build(2*node+1, mid+1, end, arr)       <- build right child
    tree[node] = tree[2*node] + tree[2*node+1]  <- combine

Walkthrough for a = [1, 3, 5, 7]:

Step 1: build(1, 0, 3)                   node=1, range=[0,3]
  Step 2: build(2, 0, 1)                 node=2, range=[0,1]
    Step 3: build(4, 0, 0) -> leaf!  tree[4] = a[0] = 1
    Step 4: build(5, 1, 1) -> leaf!  tree[5] = a[1] = 3
    tree[2] = tree[4] + tree[5] = 1 + 3 = 4
  Step 5: build(3, 2, 3)                 node=3, range=[2,3]
    Step 6: build(6, 2, 2) -> leaf!  tree[6] = a[2] = 5
    Step 7: build(7, 3, 3) -> leaf!  tree[7] = a[3] = 7
    tree[3] = tree[6] + tree[7] = 5 + 7 = 12
  tree[1] = tree[2] + tree[3] = 4 + 12 = 16

Final tree array (1-indexed):
  Index: 1   2   3   4   5   6   7
  Value: 16  4   12  1   3   5   7

Time Complexity: O(N) — each node visited exactly once
Space Complexity: O(N)

2.3 Range Query — Step by Step

Idea: Recursively traverse the tree. At each node, there are 3 cases:

query(node, node_start, node_end, query_l, query_r):

  Case 1 (No Overlap): node's range is COMPLETELY OUTSIDE query range
    if node_end < query_l OR node_start > query_r:
        return IDENTITY  (0 for sum, +INF for min, -INF for max)

  Case 2 (Complete Overlap): node's range is COMPLETELY INSIDE query range
    if query_l <= node_start AND node_end <= query_r:
        return tree[node]      <- USE pre-computed value, don't go deeper!

  Case 3 (Partial Overlap): ranges partially overlap
    mid = (node_start + node_end) / 2
    left_result  = query(2*node,   node_start, mid,      query_l, query_r)
    right_result = query(2*node+1, mid+1,      node_end, query_l, query_r)
    return left_result + right_result    <- combine

Walkthrough: Query sum[1..3] on a = [1, 3, 5, 7]

query(1, [0,3], l=1, r=3)
  -> Partial overlap
  -> Left:  query(2, [0,1], l=1, r=3)
      -> Partial overlap
      -> Left:  query(4, [0,0], l=1, r=3) -> NO OVERLAP -> return 0
      -> Right: query(5, [1,1], l=1, r=3) -> COMPLETE OVERLAP -> return tree[5]=3
      -> return 0 + 3 = 3
  -> Right: query(3, [2,3], l=1, r=3) -> COMPLETE OVERLAP -> return tree[3]=12
  -> return 3 + 12 = 15  (correct: 3+5+7=15)

Time Complexity: O(log N) — at most 4 nodes per level are "active"

2.4 Point Update — Step by Step

Idea: Update the leaf, then propagate the change upward.

update(node, node_start, node_end, idx, new_val):
    if node_start == node_end:     <- LEAF: update it
        tree[node] = new_val
        return
    mid = (node_start + node_end) / 2
    if idx <= mid:
        update(2*node,   node_start, mid,      idx, new_val)   <- go left
    else:
        update(2*node+1, mid+1,      node_end, idx, new_val)   <- go right
    tree[node] = tree[2*node] + tree[2*node+1]           <- recombine on way back up

Walkthrough: Update a[1] = 10 on a = [1, 3, 5, 7]

update(1, [0,3], idx=1, val=10)
  -> 1 <= mid=1, go left
  -> update(2, [0,1], idx=1, val=10)
      -> 1 > mid=0, go right
      -> update(5, [1,1], idx=1, val=10) -> LEAF! tree[5] = 10
      -> tree[2] = tree[4] + tree[5] = 1 + 10 = 11
  -> tree[1] = tree[2] + tree[3] = 11 + 12 = 23

Path touched: 1 -> 2 -> 5  (only log N nodes!)

Time Complexity: O(log N)

2.5 Full C++ Implementation

Recursive Segment Tree (Sum)

#include <vector>
using namespace std;

class SegmentTree {
private:
    int n;
    vector<long long> tree;

    // Build: O(N)
    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node,     start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1]; // combine
    }

    // Range Sum Query: O(log N)
    long long query(int node, int node_start, int node_end, int l, int r) {
        if (node_end < l || node_start > r) return 0;          // no overlap: identity for sum
        if (l <= node_start && node_end <= r) return tree[node]; // complete overlap
        int mid = (node_start + node_end) / 2;
        long long left_val  = query(2 * node,     node_start, mid,      l, r);
        long long right_val = query(2 * node + 1, mid + 1,    node_end, l, r);
        return left_val + right_val;
    }

    // Point Update: O(log N)
    void update(int node, int node_start, int node_end, int idx, int new_val) {
        if (node_start == node_end) { // leaf
            tree[node] = new_val;
            return;
        }
        int mid = (node_start + node_end) / 2;
        if (idx <= mid)
            update(2 * node,     node_start, mid,      idx, new_val);
        else
            update(2 * node + 1, mid + 1,    node_end, idx, new_val);
        tree[node] = tree[2 * node] + tree[2 * node + 1]; // recompute after child update
    }

public:
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    void update(int idx, int new_val) {
        update(1, 0, n - 1, idx, new_val);
    }
};

// Usage:
// SegmentTree st({1, 3, 5, 7, 9, 11});
// st.query(1, 4)    -> 3+5+7+9 = 24
// st.update(2, 10)  -> a[2] becomes 10
// st.query(1, 4)    -> 3+10+7+9 = 29

Range Minimum Query (change only the combine logic!)

// For Min Segment Tree, replace the combine line with:
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
// No-overlap identity: return INT_MAX (not 0)
// Complete-overlap:    return tree[node]

Key Insight: Only the combine function and identity value change between Sum/Min/Max. The structure is identical.

2.6 Lazy Propagation

Problem: What if queries are "range updates"? e.g., "Add 5 to all elements from index 2 to 8". Without lazy propagation, a range update takes O(N). With lazy propagation: O(log N).

Core Idea: Don't push updates down immediately. Instead, store a "pending update" (lazy tag) at each node and only push it down when you need to go deeper.

Rule: When you apply an update to a node, mark it with a lazy tag.
      Before visiting children of a node, PUSH DOWN its lazy tag first.

Visual Example: Range Add Update

Array a = [1, 3, 5, 7]. Add 2 to all elements in [1, 3].

Before:  tree = [16, 4, 12, 1, 3, 5, 7]   lazy = [0, 0, 0, 0, 0, 0, 0]

update(1, [0,3], l=1, r=3, delta=2):
  -> Partial overlap
  -> Left: update(2, [0,1], l=1, r=3, delta=2)
      -> Partial overlap
      -> Left:  update(4, [0,0], l=1, r=3, delta=2) -> NO overlap -> skip
      -> Right: update(5, [1,1], l=1, r=3, delta=2) -> COMPLETE -> tree[5]+=2 = 5
      -> tree[2] = tree[4] + tree[5] = 1 + 5 = 6
  -> Right: update(3, [2,3], l=1, r=3, delta=2)
      -> COMPLETE OVERLAP for entire [2,3]!
      -> tree[3] += 2 * 2 = 12 + 4 = 16   (len=2, add 2 to sum of range)
      -> lazy[3] += 2                      DON'T go deeper, just mark!
  -> tree[1] = tree[2] + tree[3] = 6 + 16 = 22

After: tree = [22, 6, 16, 1, 5, 5, 7]   lazy = [0, 0, 2, 0, 0, 0, 0]
       lazy[3]=2 means: "both children of node 3 still need +2 each"

Push Down Operation

When we need to visit a node's children, first flush its lazy tag:

void pushDown(int node, int node_start, int node_end) {
    if (lazy[node] != 0) {
        int mid = (node_start + node_end) / 2;
        int left = 2 * node, right = 2 * node + 1;

        // Apply lazy to both children
        tree[left]  += lazy[node] * (mid - node_start + 1);
        tree[right] += lazy[node] * (node_end - mid);
        lazy[left]  += lazy[node];
        lazy[right] += lazy[node];

        lazy[node] = 0; // clear the tag
    }
}

Full Lazy Segment Tree (Range Add, Range Sum Query)

#include <vector>
using namespace std;

class LazySegTree {
private:
    int n;
    vector<long long> tree, lazy;

    void build(const vector<int>& arr, int node, int s, int e) {
        lazy[node] = 0;
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2*node,   s,     mid);
        build(arr, 2*node+1, mid+1, e);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    // Push pending update down to children
    void pushDown(int node, int s, int e) {
        if (lazy[node] == 0) return;
        int mid = (s + e) / 2;
        // Apply to left child
        tree[2*node]   += lazy[node] * (mid - s + 1);
        lazy[2*node]   += lazy[node];
        // Apply to right child
        tree[2*node+1] += lazy[node] * (e - mid);
        lazy[2*node+1] += lazy[node];
        // Clear current node's lazy tag
        lazy[node] = 0;
    }

    // Range Add: add delta to all elements in [l, r]
    void update(int node, int s, int e, int l, int r, long long delta) {
        if (r < s || e < l) return;   // no overlap
        if (l <= s && e <= r) {       // complete overlap: update & mark lazy
            tree[node] += delta * (e - s + 1);
            lazy[node] += delta;
            return;
        }
        pushDown(node, s, e);         // partial: push first, then recurse
        int mid = (s + e) / 2;
        update(2*node,   s,     mid, l, r, delta);
        update(2*node+1, mid+1, e,   l, r, delta);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    // Range Sum Query
    long long query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return tree[node];
        pushDown(node, s, e);         // push before going deeper!
        int mid = (s + e) / 2;
        return query(2*node,   s,     mid, l, r)
             + query(2*node+1, mid+1, e,   l, r);
    }

public:
    LazySegTree(const vector<int>& arr) {
        n = arr.size();
        tree.assign(4*n, 0);
        lazy.assign(4*n, 0);
        build(arr, 1, 0, n-1);
    }

    void rangeAdd(int l, int r, long long delta) {
        update(1, 0, n-1, l, r, delta);
    }

    long long rangeSum(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};

Lazy Propagation Rules — memorize these:

Complete overlap -> apply update to current node, mark lazy[node], STOP (don't go deeper).

Partial overlap -> pushDown() first, then recurse into children.

No overlap -> return immediately.

Before any query on partial overlap -> always pushDown().

3. Fenwick Tree (BIT) — From Scratch

3.1 Mental Model — The Magic of `i & (-i)`

A Fenwick Tree (Binary Indexed Tree / BIT) is a cleverly indexed array that uses binary representations of indices to store partial sums.

The Core Trick: i & (-i) (Lowest Set Bit)

In binary:
  i        = 0 1 1 0 1 0 0 0   (e.g., i = 104)
  -i       = 1 0 0 1 1 0 0 0   (two's complement)
  i & (-i) = 0 0 0 0 1 0 0 0   = 8   the lowest set bit!

This extracts the position of the lowest set bit (LSB), which controls what range each BIT node covers.

What does BIT[i] store?

BIT[i] stores the sum of elements from index i - LSB(i) + 1 to i.

Index i  Binary   LSB  Range that BIT[i] covers
      0001     1    [1..1]    = a[1]
      0010     2    [1..2]    = a[1]+a[2]
      0011     1    [3..3]    = a[3]
      0100     4    [1..4]    = a[1]+a[2]+a[3]+a[4]
      0101     1    [5..5]    = a[5]
      0110     2    [5..6]    = a[5]+a[6]
      0111     1    [7..7]    = a[7]
      1000     8    [1..8]    = a[1]+...+a[8]

Visual for array a = [_, 1, 3, 5, 7, 9, 11, 13, 15] (1-indexed):

BIT[8]=64  covers [1..8]     (entire array sum)
BIT[4]=16  covers [1..4]
BIT[6]=20  covers [5..6]
BIT[2]=4   covers [1..2]
BIT[1]=1   covers [1..1]
BIT[3]=5   covers [3..3]
BIT[5]=9   covers [5..5]
BIT[7]=13  covers [7..7]

3.2 Building the Tree

Simple approach: Start with all zeros, then do N point updates. Each update is O(log N), total: O(N log N).

Optimal O(N) build:

void build(vector<int>& arr) {
    // arr is 1-indexed, arr[0] is unused
    for (int i = 1; i <= n; i++) {
        bit[i] += arr[i];              // update current node
        int parent = i + (i & -i);    // find responsible parent
        if (parent <= n)
            bit[parent] += bit[i];    // propagate up
    }
}

3.3 Prefix Sum Query

To compute sum(1, i) = a[1] + a[2] + ... + a[i]:

Algorithm: Walk backwards by repeatedly removing the lowest set bit.

prefixSum(i):
    sum = 0
    while i > 0:
        sum += BIT[i]
        i -= (i & -i)     <- remove lowest set bit, jump to "parent"
    return sum

Walkthrough: prefixSum(7) on a = [_, 1, 3, 5, 7, 9, 11, 13]

i=7 (0111): BIT[7]=13  -> sum=13,  i = 7 - 1 = 6
i=6 (0110): BIT[6]=20  -> sum=33,  i = 6 - 2 = 4
i=4 (0100): BIT[4]=16  -> sum=49,  i = 4 - 4 = 0
i=0: STOP

prefixSum(7) = 49 = 1+3+5+7+9+11+13  (correct!)

Range Sum Query: sum(l, r) = prefixSum(r) - prefixSum(l-1)

3.4 Point Update

To add delta to a[i] (propagate to all BIT nodes covering index i):

Algorithm: Walk forward by repeatedly adding the lowest set bit.

update(i, delta):
    while i <= n:
        BIT[i] += delta
        i += (i & -i)     <- add lowest set bit, jump to next responsible node

Walkthrough: Update a[3] by +10

i=3 (0011): BIT[3]+=10  ->  i = 3 + 1 = 4
i=4 (0100): BIT[4]+=10  ->  i = 4 + 4 = 8
i=8 (1000): BIT[8]+=10  ->  i = 8 + 8 = 16  -> 16 > n, STOP

Only 3 nodes updated — O(log N)!

Why does this work? Index 3 is covered by BIT[3], BIT[4], and BIT[8]. By adding the LSB repeatedly, we traverse exactly those nodes.

3.5 Full C++ Implementation

#include <vector>
using namespace std;

class FenwickTree {
private:
    int n;
    vector<long long> bit; // 1-indexed

public:
    // Initialize with all zeros: O(N)
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    // Initialize from array (0-indexed input): O(N log N)
    FenwickTree(const vector<int>& arr) : n(arr.size()), bit(arr.size() + 1, 0) {
        for (int i = 0; i < n; i++)
            update(i + 1, arr[i]); // convert 0-indexed arr to 1-indexed BIT
    }

    // Add delta to position i (1-indexed): O(log N)
    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i))
            bit[i] += delta;
    }

    // Prefix sum [1..i] (1-indexed): O(log N)
    long long prefixSum(int i) {
        long long sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += bit[i];
        return sum;
    }

    // Range sum [l..r] (1-indexed): O(log N)
    long long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }

    // Point query at index i: O(log N)
    long long pointQuery(int i) {
        return rangeSum(i, i);
    }

    // Set a[i] to new_val: O(log N)
    void set(int i, long long new_val) {
        long long curr = pointQuery(i);
        update(i, new_val - curr);
    }
};

// Usage (0-indexed array, convert to 1-indexed internally):
// FenwickTree ft({1, 3, 5, 7, 9, 11});
// ft.rangeSum(2, 5)  -> a[2]+a[3]+a[4]+a[5] = 5+7+9+11 = 32 (1-indexed [2,5])
// ft.update(3, 4)    -> a[3] += 4 (1-indexed)

3.6 Range Update + Range Query (Advanced BIT)

Standard BIT supports point update + prefix sum query. To support range update + range sum query, use two BITs with a math trick.

Math Trick: Let D[i] be a difference array where D[i] = a[i] - a[i-1].

Then after expansion: prefix_sum(a, r) = (r+1) * sum(D[j]) - sum(j * D[j])

So we maintain two BITs:

bit1[i] stores D[i]
bit2[i] stores i * D[i]

class AdvancedBIT {
private:
    int n;
    vector<long long> bit1, bit2;

    void add(vector<long long>& bit, int i, long long v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    long long sum(vector<long long>& bit, int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

    long long prefixSum(int i) {
        return sum(bit1, i) * (i + 1) - sum(bit2, i);
    }

public:
    AdvancedBIT(int n) : n(n), bit1(n+1, 0), bit2(n+1, 0) {}

    // Add delta to all elements in [l, r]: O(log N)
    void rangeAdd(int l, int r, long long delta) {
        add(bit1, l,    delta);
        add(bit1, r+1, -delta);
        add(bit2, l,    delta * l);
        add(bit2, r+1, -delta * (r+1));
    }

    // Sum of [l, r]: O(log N)
    long long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

4. Segment Tree vs Fenwick Tree — Decision Guide

When to Choose Which?

                    START
                      |
         +------------v------------+
         | Do you only need SUM    |
         | queries (not min/max)?  |
         +------------+------------+
                      |
              YES ----+---- NO
              |                |
              |           -> Use SEGMENT TREE (more flexible)
              |
   +----------v----------+
   | Are updates POINT   |
   | updates only?       |
   +----------+----------+
              |
       YES ---+--- NO (range updates needed)
       |               |
       |         -> ADVANCED BIT (2 BITs) or LAZY SEGMENT TREE
       |
   +---v-------------------+
   | Prefer simpler code?  |
   +---+-------------------+
       |
 YES --+-- NO (need max performance)
   |           |
   |       Both work; Fenwick has better constant factor
   |
-> Use FENWICK TREE (simpler, faster constants)

Side-by-Side Comparison

Feature	Segment Tree	Fenwick Tree
Code Complexity	High (50+ lines)	Low (~15 lines)
Point Update	O(log N)	O(log N)
Range Sum Query	O(log N)	O(log N)
Range Min/Max Query	O(log N)	Not directly
Range Update (add)	O(log N) with lazy	O(log N) with 2 BITs
Range Update (set)	O(log N) with lazy	Complex
Constant Factor	Higher (~2x slower)	Lower (cache-friendly)
Space	4N	N+1
2D Extension	Possible but complex	Very natural (2D BIT)

Quick Decision Summary

Use Case	Choose
Range sum + point update	Fenwick Tree (simpler, faster)
Range minimum / maximum query	Segment Tree
Range sum + range update (add)	Advanced BIT or Lazy Seg Tree
Range assign + range query	Lazy Segment Tree
Count of elements in range	Segment Tree or BIT + coordinate compression
Competitive programming speed	Fenwick for sums; Seg Tree otherwise

5. Common Variants & Extensions

5.1 Segment Tree with Different Aggregates

// Just change the combine function and identity value:

// Min Segment Tree:
tree[node] = min(tree[2*node], tree[2*node+1]);
// identity = INT_MAX

// Max Segment Tree:
tree[node] = max(tree[2*node], tree[2*node+1]);
// identity = INT_MIN

// GCD Segment Tree:
tree[node] = __gcd(tree[2*node], tree[2*node+1]);
// identity = 0

// XOR Segment Tree:
tree[node] = tree[2*node] ^ tree[2*node+1];
// identity = 0

// Product Segment Tree (with MOD):
tree[node] = (tree[2*node] * tree[2*node+1]) % MOD;
// identity = 1

5.2 Generic Template Segment Tree

template<typename T>
class GenericSegTree {
    int n;
    vector<T> tree;
    T identity;
    function<T(T,T)> combine;

    void build(const vector<T>& arr, int node, int s, int e) {
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2*node, s, mid);
        build(arr, 2*node+1, mid+1, e);
        tree[node] = combine(tree[2*node], tree[2*node+1]);
    }
    T query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return identity;
        if (l <= s && e <= r) return tree[node];
        int mid = (s + e) / 2;
        return combine(query(2*node, s, mid, l, r),
                       query(2*node+1, mid+1, e, l, r));
    }
    void update(int node, int s, int e, int idx, T val) {
        if (s == e) { tree[node] = val; return; }
        int mid = (s + e) / 2;
        if (idx <= mid) update(2*node, s, mid, idx, val);
        else            update(2*node+1, mid+1, e, idx, val);
        tree[node] = combine(tree[2*node], tree[2*node+1]);
    }
public:
    GenericSegTree(const vector<T>& arr, T identity, function<T(T,T)> combine)
        : n(arr.size()), tree(4*arr.size()), identity(identity), combine(combine) {
        build(arr, 1, 0, n-1);
    }
    T query(int l, int r) { return query(1, 0, n-1, l, r); }
    void update(int idx, T val) { update(1, 0, n-1, idx, val); }
};

// Usage:
// GenericSegTree<int> minTree(arr, INT_MAX, [](int a, int b){ return min(a,b); });
// GenericSegTree<int> sumTree(arr, 0, [](int a, int b){ return a+b; });

5.3 2D Fenwick Tree (Matrix Range Sum)

class BIT2D {
    int n, m;
    vector<vector<long long>> bit;
public:
    BIT2D(int n, int m) : n(n), m(m), bit(n+1, vector<long long>(m+1, 0)) {}

    void update(int x, int y, long long v) {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
                bit[i][j] += v;
    }

    long long query(int x, int y) {
        long long s = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                s += bit[i][j];
        return s;
    }

    // Sum in rectangle (x1,y1) to (x2,y2): inclusion-exclusion
    long long rangeQuery(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1-1, y2)
             - query(x2, y1-1) + query(x1-1, y1-1);
    }
};

6. 10 Practice Problems with Full Solutions

Problem 1: Range Sum Query — Mutable (LeetCode 307)

Problem: Implement a data structure supporting:

update(index, val): Update a[index] to val.
sumRange(left, right): Return a[left] + ... + a[right].

Pattern Signal: "Range query + point update" -> Fenwick Tree

class NumArray {
    int n;
    vector<long long> bit;
    vector<int> arr;

    void bit_update(int i, long long delta) {
        for (i++; i <= n; i += i & -i) bit[i] += delta;
    }
    long long prefix(int i) {
        long long s = 0;
        for (i++; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

public:
    NumArray(vector<int>& nums) : n(nums.size()), bit(nums.size()+1, 0), arr(nums) {
        for (int i = 0; i < n; i++) bit_update(i, nums[i]);
    }

    void update(int index, int val) {
        bit_update(index, val - arr[index]); // add the delta
        arr[index] = val;
    }

    int sumRange(int left, int right) {
        return prefix(right) - (left > 0 ? prefix(left-1) : 0);
    }
};
// Time: O(log N) per operation | Space: O(N)

Problem 2: Range Minimum Query

Problem: Given array, answer multiple queries: what is the minimum in [l, r]?

class RMQ {
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int node, int s, int e) {
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2*node, s, mid);
        build(arr, 2*node+1, mid+1, e);
        tree[node] = min(tree[2*node], tree[2*node+1]); // min combine!
    }

    int query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return INT_MAX; // identity for min
        if (l <= s && e <= r) return tree[node];
        int mid = (s + e) / 2;
        return min(query(2*node, s, mid, l, r),
                   query(2*node+1, mid+1, e, l, r));
    }

public:
    RMQ(const vector<int>& arr) : n(arr.size()), tree(4*arr.size()) {
        build(arr, 1, 0, n-1);
    }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
};

Problem 3: Count of Smaller Numbers After Self (LeetCode 315)

Problem: For each element, count how many elements to its right are smaller.

Pattern: Process right-to-left. Use BIT + coordinate compression to count smaller elements.

vector<int> countSmaller(vector<int>& nums) {
    int n = nums.size();
    // Coordinate compress to [1, m]
    vector<int> sorted_nums = nums;
    sort(sorted_nums.begin(), sorted_nums.end());
    sorted_nums.erase(unique(sorted_nums.begin(), sorted_nums.end()), sorted_nums.end());
    int m = sorted_nums.size();

    auto compress = [&](int v) -> int {
        return lower_bound(sorted_nums.begin(), sorted_nums.end(), v)
               - sorted_nums.begin() + 1; // 1-indexed
    };

    vector<long long> bit(m + 2, 0);
    auto bit_update = [&](int i) {
        for (; i <= m; i += i & -i) bit[i]++;
    };
    auto bit_query = [&](int i) -> long long {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };

    vector<int> result(n);
    for (int i = n - 1; i >= 0; i--) {
        int ci = compress(nums[i]);
        result[i] = bit_query(ci - 1); // count elements with compressed value < ci
        bit_update(ci);                 // insert nums[i]
    }
    return result;
}
// Time: O(N log N) | Space: O(N)

Problem 4: Range Sum with Range Update

Problem: Array of zeros, support:

add(l, r, v): Add v to all elements in [l, r].
sum(l, r): Return sum of [l, r].

Solution: Advanced BIT (two BITs):

int n;
long long bit1[100005], bit2[100005];

void add(long long* bit, int i, long long v) {
    for (; i <= n; i += i & -i) bit[i] += v;
}
long long sum(long long* bit, int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

void rangeAdd(int l, int r, long long v) {
    add(bit1, l,    v);     add(bit1, r+1, -v);
    add(bit2, l,    v*l);   add(bit2, r+1, -v*(r+1));
}

long long prefixSum(int i) {
    return sum(bit1, i) * (i + 1) - sum(bit2, i);
}

long long rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

Problem 5: Falling Squares (LeetCode 699)

Problem: Squares fall onto a number line. After each square falls, return max height.

Key Insight: Coordinate compression + Lazy Seg Tree (range-assign + range-max).

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        // Coordinate compress all x-coordinates
        vector<int> coords;
        for (auto& p : positions) {
            coords.push_back(p[0]);
            coords.push_back(p[0] + p[1]);
        }
        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());
        int m = coords.size();

        auto getIdx = [&](int v) {
            return (int)(lower_bound(coords.begin(), coords.end(), v) - coords.begin());
        };

        // Lazy Seg Tree for range-set + range-max
        vector<int> tree(4*m, 0), lazy(4*m, -1);

        function<void(int,int,int)> pushDown = [&](int node, int s, int e) {
            if (lazy[node] != -1) {
                tree[2*node] = tree[2*node+1] = lazy[node];
                lazy[2*node] = lazy[2*node+1] = lazy[node];
                lazy[node] = -1;
            }
        };

        function<void(int,int,int,int,int,int)> update = [&](int nd, int s, int e, int l, int r, int val) {
            if (r <= s || e <= l) return;
            if (l <= s && e <= r) { tree[nd] = val; lazy[nd] = val; return; }
            pushDown(nd, s, e);
            int mid = (s + e) / 2;
            update(2*nd, s, mid, l, r, val);
            update(2*nd+1, mid, e, l, r, val);
            tree[nd] = max(tree[2*nd], tree[2*nd+1]);
        };

        function<int(int,int,int,int,int)> query = [&](int nd, int s, int e, int l, int r) -> int {
            if (r <= s || e <= l) return 0;
            if (l <= s && e <= r) return tree[nd];
            pushDown(nd, s, e);
            int mid = (s + e) / 2;
            return max(query(2*nd, s, mid, l, r), query(2*nd+1, mid, e, l, r));
        };

        vector<int> result;
        int globalMax = 0;
        for (auto& p : positions) {
            int l = getIdx(p[0]), r = getIdx(p[0] + p[1]);
            int h = query(1, 0, m, l, r) + p[1];
            update(1, 0, m, l, r, h);
            globalMax = max(globalMax, h);
            result.push_back(globalMax);
        }
        return result;
    }
};

Problem 6: Number of Inversions

Problem: Count pairs (i, j) where i < j but a[i] > a[j].

int countInversions(vector<int>& arr) {
    int n = arr.size();
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    int m = sorted_arr.size();

    vector<long long> bit(m + 1, 0);
    auto update = [&](int i) { for (; i <= m; i += i & -i) bit[i]++; };
    auto query  = [&](int i) { long long s=0; for (; i>0; i-=i&-i) s+=bit[i]; return s; };

    int inversions = 0;
    for (int i = n - 1; i >= 0; i--) {
        int ci = (int)(lower_bound(sorted_arr.begin(), sorted_arr.end(), arr[i])
                 - sorted_arr.begin()) + 1;
        inversions += query(ci - 1); // count elements already seen that are < arr[i]
        update(ci);
    }
    return inversions;
}
// Time: O(N log N)

Problem 7: Longest Increasing Subsequence in O(N log N) via BIT

Problem: Find the length of the longest strictly increasing subsequence (LIS).

int LIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();

    // bit[i] = max LIS length achievable using elements with compressed value <= i
    vector<int> bit(m + 1, 0);

    auto update = [&](int i, int val) {
        for (; i <= m; i += i & -i) bit[i] = max(bit[i], val);
    };
    auto query = [&](int i) {
        int mx = 0;
        for (; i > 0; i -= i & -i) mx = max(mx, bit[i]);
        return mx;
    };

    int result = 0;
    for (int x : nums) {
        int ci = (int)(lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin()) + 1;
        int best = query(ci - 1) + 1; // best LIS ending just before x
        update(ci, best);
        result = max(result, best);
    }
    return result;
}
// Time: O(N log N) — equivalent to patience sorting

Problem 8: Range GCD Queries

Problem: Given array, find GCD of all elements in range [l, r].

Key: Segment Tree with GCD as the combine function. GCD has gcd(a, 0) = a as identity.

class GCDTree {
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int node, int s, int e) {
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2*node, s, mid);
        build(arr, 2*node+1, mid+1, e);
        tree[node] = __gcd(tree[2*node], tree[2*node+1]); // GCD combine
    }

    int query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0; // identity for GCD is 0 (gcd(x,0)=x)
        if (l <= s && e <= r) return tree[node];
        int mid = (s + e) / 2;
        return __gcd(query(2*node, s, mid, l, r),
                     query(2*node+1, mid+1, e, l, r));
    }

public:
    GCDTree(const vector<int>& arr) : n(arr.size()), tree(4*arr.size()) {
        build(arr, 1, 0, n-1);
    }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
};

Problem 9: Maximum Subarray Sum in Range (Composite Node Seg Tree)

Problem: Support queries: what is the maximum subarray sum within [l, r]?

Key Insight: Each node stores 4 values — total sum, max prefix, max suffix, max subarray.

struct Node {
    long long total;   // total sum of range
    long long pref;    // max prefix sum
    long long suf;     // max suffix sum
    long long ans;     // max subarray sum
};

Node combine(Node L, Node R) {
    return {
        L.total + R.total,
        max(L.pref, L.total + R.pref),
        max(R.suf,  R.total + L.suf),
        max({L.ans, R.ans, L.suf + R.pref})
    };
}

Node makeLeaf(int v) {
    long long val = v;
    return {val, max(val, 0LL), max(val, 0LL), max(val, 0LL)};
}

// Build with combine(left_child, right_child)
// Query returns Node; use node.ans for the answer
// Time: O(log N) per query with full range-max-subarray support

Problem 10: 2D Range Sum Query (LeetCode 308 — Matrix)

Problem: Given a 2D matrix, support update(row, col, val) and sumRegion(r1,c1,r2,c2).

Solution: 2D Fenwick Tree

class NumMatrix {
    int n, m;
    vector<vector<long long>> bit;
    vector<vector<int>> mat;

    void bit_update(int x, int y, long long v) {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
                bit[i][j] += v;
    }

    long long prefix(int x, int y) {
        long long s = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                s += bit[i][j];
        return s;
    }

public:
    NumMatrix(vector<vector<int>>& matrix)
        : n(matrix.size()), m(matrix[0].size()),
          bit(n+1, vector<long long>(m+1, 0)), mat(matrix) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                bit_update(i+1, j+1, matrix[i][j]);
    }

    void update(int row, int col, int val) {
        bit_update(row+1, col+1, val - mat[row][col]);
        mat[row][col] = val;
    }

    int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix(r2+1, c2+1) - prefix(r1, c2+1)
             - prefix(r2+1, c1) + prefix(r1, c1);
    }
};
// Time: O(log N * log M) per operation

7. Interview Cheat Sheet

Segment Tree — 5-Line Mental Model

Build:  Recurse to leaf -> leaf stores value -> parent = combine(left, right)
Query:  3 cases: no-overlap (identity), complete-overlap (return node), partial (recurse both)
Update: Walk to leaf -> update leaf -> recompute parents on way back up
Lazy:   Complete-overlap -> mark lazy, don't recurse deeper
           Partial-overlap -> pushDown FIRST, then recurse
Size:   4*N array, 1-indexed, left=2i, right=2i+1

Fenwick Tree — 3-Line Mental Model

BIT[i] covers range [i - LSB(i) + 1, i] where LSB(i) = i & (-i)
Query(i):  sum=0; while i>0 { sum+=bit[i]; i-=i&-i; }  (remove LSB = walk left)
Update(i): while i<=n { bit[i]+=v; i+=i&-i; }           (add LSB = walk right)

Complexity Reference

Operation	Segment Tree	Fenwick Tree
Build	O(N)	O(N log N)
Point Update	O(log N)	O(log N)
Range Sum	O(log N)	O(log N)
Range Min/Max	O(log N)	Not supported
Range Update + Range Sum	O(log N) lazy	O(log N) 2-BIT
Space	4N	N+1

Interview Recognition Signals

Signal in Problem	Data Structure
"range sum / range min / range max" + "point update"	Segment Tree or Fenwick
"prefix sum" + "point update"	Fenwick Tree (simpler)
"range update" + "range query"	Lazy Segment Tree or 2-BIT
"count of elements <= X" while inserting	Fenwick Tree + coordinate compress
"number of inversions"	Fenwick Tree
"k-th smallest in range"	Persistent Segment Tree
"max subarray sum in range"	Segment Tree (composite node)
"rectangle area union"	Segment Tree + sweep line

Common Bugs to Avoid

// BUG 1: Off-by-one — BIT is 1-indexed, arrays are 0-indexed
for (int i = 0; i < n; i++) update(i + 1, arr[i]); // always +1

// BUG 2: Segment Tree array too small — always use 4*N
vector<int> tree(4 * n, 0); // NOT 2*n

// BUG 3: Forgetting pushDown in Lazy Seg Tree
// Always pushDown(node, s, e) BEFORE computing mid and recursing!

// BUG 4: Wrong identity for no-overlap
// Sum -> 0, Min -> INT_MAX, Max -> INT_MIN, GCD -> 0, XOR -> 0

// BUG 5: Lazy: update tree[child] by length of child's range (not parent's)
tree[2*node]   += lazy[node] * (mid - s + 1);  // left child length
tree[2*node+1] += lazy[node] * (e - mid);       // right child length

// BUG 6: Integer overflow — always use long long for sums
vector<long long> tree(4 * n, 0LL);

Templates to Memorize

Fenwick (Point Update + Prefix Sum) — 3 functions, 3 lines each:

void update(int i, int v) { for(; i<=n; i+=i&-i) bit[i]+=v; }
int  query (int i)        { int s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; }
int  range (int l, int r) { return query(r) - query(l-1); }

Segment Tree Query (3 cases):

T query(int node, int s, int e, int l, int r) {
    if (r<s || e<l) return IDENTITY;             // no overlap
    if (l<=s && e<=r) return tree[node];          // complete overlap
    int mid=(s+e)/2;                              // partial overlap
    return combine(query(2*node,  s,mid,  l,r),
                   query(2*node+1,mid+1,e,l,r));
}

Lazy Push Down (Range Add):

void pushDown(int node, int s, int e) {
    if (!lazy[node]) return;
    int mid = (s+e)/2;
    tree[2*node]   += lazy[node]*(mid-s+1);   lazy[2*node]   += lazy[node];
    tree[2*node+1] += lazy[node]*(e-mid);     lazy[2*node+1] += lazy[node];
    lazy[node] = 0;
}

📅 Study Roadmap for This Topic

Day 1: Mental Model
  [ ] Read Sections 1, 2.1, 2.2
  [ ] Draw the Segment Tree on paper for array [2, 4, 6, 8, 10]
  [ ] Implement build() from scratch without looking

Day 2: Segment Tree Operations
  [ ] Implement query() — dry-run the 3 cases on paper first
  [ ] Implement update() — trace the path
  [ ] Solve Problems 1 and 2

Day 3: Fenwick Tree
  [ ] Read Section 3.1 — play with i & (-i) in binary on paper
  [ ] Implement prefixSum/update from scratch
  [ ] Solve Problem 6 (inversions)

Day 4: Lazy Propagation
  [ ] Read Section 2.6 very carefully — understand pushDown
  [ ] Implement LazySegTree from scratch
  [ ] Solve Problems 4 and 5

Day 5: Advanced & Variants
  [ ] Read Generic Seg Tree, 2D BIT (Section 5)
  [ ] Solve Problems 3, 7, 8

Day 6-7: Mock Interview Drill
  [ ] Solve Problems 9, 10
  [ ] Review cheat sheet
  [ ] Time yourself: Fenwick Tree in 5 mins, Segment Tree in 10 mins

This module is part of the DSA Mastery Roadmap. Back to: Module 10 — Advanced Data Structures.

12-segment-tree-and-fenwick-tree.md