DEV Community

DevCorner2
DevCorner2

Posted on

🔥 Blog 3: Segment Tree & Fenwick Tree (BIT) — Range Queries Made Easy

In competitive programming and interviews, range queries (like "find sum of elements from index L to R" or "find minimum in a subarray") are extremely common.

Naïve solutions often take O(n) per query, which is too slow for large inputs. To handle millions of queries efficiently, we use Segment Trees and Fenwick Trees.

🔹 Problem Statement

You’re given an array of numbers and must support operations like:

  1. Range Sum Query: sum(L, R)
  2. Range Minimum/Maximum Query: min(L, R)
  3. Point Updates: update a single index efficiently

1️⃣ Segment Tree

🧠 Idea:

  • Represent the array as a binary tree, where each node stores information about a segment (range).
  • Build time = O(n), Query & Update time = O(log n).

✅ Example: Range Sum Segment Tree 

class SegmentTree {
    int[] tree;
    int n;

    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n]; // safe size
        build(arr, 0, n - 1, 1);
    }

    void build(int[] arr, int start, int end, int node) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, start, mid, 2 * node);
        build(arr, mid + 1, end, 2 * node + 1);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

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

    int queryUtil(int start, int end, int l, int r, int node) {
        if (r < start || end < l) return 0; // no overlap
        if (l <= start && end <= r) return tree[node]; // full overlap
        int mid = (start + end) / 2;
        return queryUtil(start, mid, l, r, 2 * node) +
               queryUtil(mid + 1, end, l, r, 2 * node + 1);
    }

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

    void updateUtil(int start, int end, int idx, int val, int node) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) updateUtil(start, mid, idx, val, 2 * node);
        else updateUtil(mid + 1, end, idx, val, 2 * node + 1);

        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree seg = new SegmentTree(arr);

        System.out.println("Sum(1,3) = " + seg.query(1, 3)); // 15
        seg.update(1, 10);
        System.out.println("Sum(1,3) after update = " + seg.query(1, 3)); // 22
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Output Example:

Sum(1,3) = 15
Sum(1,3) after update = 22
Enter fullscreen mode Exit fullscreen mode

2️⃣ Fenwick Tree (Binary Indexed Tree - BIT)

🧠 Idea:

  • Space-efficient alternative to Segment Tree.
  • Uses prefix sums + binary representation to handle updates and queries in O(log n).
  • More compact than Segment Trees but harder for range min/max.

✅ Example: Fenwick Tree (Range Sum) 

class FenwickTree {
    int[] BIT;
    int n;

    FenwickTree(int n) {
        this.n = n;
        BIT = new int[n + 1];
    }

    void update(int idx, int val) {
        idx++;
        while (idx <= n) {
            BIT[idx] += val;
            idx += idx & -idx; // move to parent
        }
    }

    int query(int idx) {
        idx++;
        int sum = 0;
        while (idx > 0) {
            sum += BIT[idx];
            idx -= idx & -idx; // move to ancestor
        }
        return sum;
    }

    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        FenwickTree ft = new FenwickTree(arr.length);

        for (int i = 0; i < arr.length; i++) {
            ft.update(i, arr[i]);
        }

        System.out.println("Sum(1,3) = " + ft.rangeQuery(1, 3)); // 15
        ft.update(1, 7); // increase arr[1] by 7 (3 → 10)
        System.out.println("Sum(1,3) after update = " + ft.rangeQuery(1, 3)); // 22
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Output Example:

Sum(1,3) = 15
Sum(1,3) after update = 22
Enter fullscreen mode Exit fullscreen mode

🔹 Segment Tree vs Fenwick Tree

Feature Segment Tree Fenwick Tree
Build Time O(n) O(n log n)
Query Time O(log n) O(log n)
Update Time O(log n) O(log n)
Memory O(4n) O(n)
Supports RMQ (min/max) ✅ Yes ❌ No
Easier to Code ❌ More complex ✅ Simpler

🔹 Interview Problem Examples

  • [LeetCode 307] Range Sum Query - Mutable (Segment Tree, BIT)
  • [LeetCode 308] Range Sum Query 2D (Segment Tree)
  • [LeetCode 315] Count of Smaller Numbers After Self (Fenwick Tree)
  • [GFG] Inversion Count (Fenwick Tree)

✅ Key Takeaways

  • Segment Tree → general purpose, handles sum, min, max, GCD, etc.
  • Fenwick Tree (BIT) → lightweight, great for range sum + updates.
  • Both give O(log n) per query/update, critical for performance.

👉 Next in this series (Blog 4) we’ll cover Pattern 16: Disjoint Set Union (Union-Find with Path Compression & Union by Rank) — the backbone of graph connectivity and Kruskal’s MST.

Top comments (0)