Range Query Data Structures

This article covers the two main range-query data structures that go beyond prefix sums when updates also matter.

1. Intuition

Prefix sums are great for static data. Once updates appear, you need a structure that can both:

• update values efficiently
• answer range queries efficiently

That is where segment trees and Fenwick trees help.

2. How It Works

• Segment tree stores answers for intervals in a binary-tree structure
• Fenwick tree stores partial sums using bit tricks and is ideal for prefix-based operations

3. Pattern Recognition

Think of these structures when you see:

• many range sum queries with updates
• range minimum or maximum queries
• dynamic prefix totals

4. Dry Run Example

Input:

nums = [1, 3, 5, 7, 9, 11]
query sum(1..3), then update index 2 to 6

Step-by-step execution:

• data structure answers 3 + 5 + 7 = 15
• update changes all affected parent ranges
• next queries use the new value immediately

5. Code (C++)

class Fenwick {
 public:
  explicit Fenwick(int n) : bit(n + 1, 0) {}

  void add(int index, int delta) {
    for (index++; index < static_cast<int>(bit.size()); index += index & -index) {
      bit[index] += delta;
    }
  }

  int sumPrefix(int index) const {
    int answer = 0;
    for (index++; index > 0; index -= index & -index) {
      answer += bit[index];
    }
    return answer;
  }

 private:
  vector<int> bit;
};

6. Complexity Analysis

• Segment tree: O(log n) update and query
• Fenwick tree: O(log n) update and prefix query

7. When to Use

• online range queries
• frequent point updates
• inversion count and order-statistic style problems

8. Common Mistakes

• mixing 0-based and 1-based indexing in Fenwick trees
• overusing segment tree when prefix-only behavior is enough

9. Variations / Extensions

• lazy propagation
• range update + range query
• segment tree for min, max, gcd, or custom merges

10. LeetCode Practice Problems

Medium

• https://magicsheet.dev/questions/range-sum-query-mutable/

Hard

• https://magicsheet.dev/questions/count-of-smaller-numbers-after-self/

11. Key Takeaways

• Segment tree is more general
• Fenwick tree is lighter and perfect for prefix-based range sums
• Learn prefix sums first, then move here when updates appear

Back: Advanced Strings, Bits, Math, and Range Queries