Range Query Overview

​

Introduction

• Range Sum/Min/Max: Find aggregate values over a range
• Range Updates: Modify multiple elements efficiently
• Point Queries: Access individual elements after updates

​

Choosing the Right Structure

​

Segment Tree

• Best for: General range queries with range updates
• Supports: Any associative operation
• Updates: O(log n) point and range updates
• Queries: O(log n)
• Space: O(4n)

​

Fenwick Tree (BIT)

• Best for: Prefix sums and frequency counting
• Supports: Operations with inverse (addition/subtraction)
• Updates: O(log n) point updates
• Queries: O(log n) prefix queries
• Space: O(n)

​

Sparse Table

• Best for: Static arrays with idempotent operations
• Supports: min, max, gcd (operations where f(x,x) = x)
• Updates: Not supported (static)
• Queries: O(1)
• Space: O(n log n)

​

Common Use Cases

​

Range Sum Queries

// Fenwick Tree - most efficient
fenwick<int> ft(n);
ft.modify(i, val);  // Add val to position i
int sum = ft.query(r) - ft.query(l-1);  // Sum [l, r]

​

Range Minimum Query (RMQ)

// Sparse Table - O(1) queries on static array
auto func = [](int x, int y) { return min(x, y); };
SparseTMin<int> st(values);
int min_val = st.query(l, r);  // O(1)

​

Range Updates with Lazy Propagation

// Segment Tree with lazy propagation
segtree<int> st(n);
st.modify(l, r, val);  // Set all elements in [l, r] to val
auto result = st.query(l, r);  // Get sum, min, max

​

Performance Comparison

​

Next Steps

1. Segment Tree - Learn about basic and lazy propagation variants
2. Fenwick Tree - Master efficient prefix sum queries
3. Sparse Table - Understand O(1) RMQ for static arrays