Segment Trees & Fenwick Trees

Segment Trees & Fenwick Trees

Why This Matters

Segment trees and Fenwick trees (Binary Indexed Trees) are advanced data structures optimized for range queries and updates. Unlike arrays that require O(n) time for range queries, these trees provide O(log n) time for both queries and updates.

This matters because many real-world problems involve range operations. Need the sum of elements from index 5 to 20? A naive approach scans all elements (O(n)). A segment tree or Fenwick tree does this in O(log n). This makes them essential for problems involving range sums, minimums, maximums, and other aggregate operations.

In interviews, these structures test your understanding of advanced tree algorithms and your ability to optimize for specific operation patterns. Real-world systems use them extensively: databases use segment trees for range indexes, financial systems use them for time-series range queries, and game engines use them for spatial queries.

What Engineers Usually Get Wrong

Most engineers think "segment trees and Fenwick trees are the same." While both solve range query problems, they have important differences. Fenwick trees are simpler and use less space, but only support sum queries efficiently. Segment trees are more flexible (support min, max, gcd, custom functions) but use more space and are more complex.

Engineers also overuse these structures. For simple range sum queries on static arrays, prefix sums are O(1) query time and much simpler. Segment trees and Fenwick trees are only worth it when you need updates.

Another common mistake is incorrect implementation of lazy propagation (for range updates in segment trees). Lazy propagation is tricky—you must correctly propagate lazy values during queries and updates, and handle edge cases like overlapping ranges.

How This Breaks Systems in the Real World

A financial system was tracking stock prices over time. It needed to answer queries like "what was the maximum price between 9 AM and 3 PM?" The system used a simple array and scanned the range for each query (O(n)). During market hours, thousands of queries per second made the system slow. The fix? Use a segment tree. Range max queries became O(log n), making the system fast enough to handle real-time queries.

Another story: A database was using B-trees for range queries on a numeric column. For queries like "sum of values between 100 and 500", the database had to scan many B-tree nodes. The fix? Add a segment tree index alongside the B-tree. Range sum queries became O(log n) instead of O(n), dramatically improving query performance.

Segment Trees

A segment tree is a binary tree where each node represents a segment (range) of the array. The root represents the entire array, and leaves represent individual elements.

Structure

For array [1, 3, 5, 7, 9, 11]:

                    [0-5: 36]
                   /          \
            [0-2: 9]          [3-5: 27]
           /        \          /        \
      [0-1: 4]   [2: 5]   [3-4: 16]   [5: 11]
      /      \              /      \
  [0: 1]  [1: 3]      [3: 7]  [4: 9]

Each node stores the aggregate (sum, min, max, etc.) for its range.

Implementation (Range Sum Query)

1class SegmentTree {
2  private tree: number[];
3  private n: number;
4
5  constructor(arr: number[]) {
6    this.n = arr.length;
7    this.tree = new Array(4 * this.n).fill(0);
8    this.build(arr, 0, 0, this.n - 1);
9  }

Fenwick Trees (Binary Indexed Trees)

A Fenwick tree is a simpler alternative to segment trees for range sum queries. It uses less space (O(n) vs O(4n)) and is easier to implement, but only supports sum queries efficiently.

Key Insight

Each index i in the Fenwick tree stores the sum of a range determined by the binary representation of i. The range for index i is from i - 2^lsb(i) + 1 to i, where lsb(i) is the least significant bit.

Implementation

1class FenwickTree {
2  private tree: number[];
3  private n: number;
4
5  constructor(arr: number[]) {
6    this.n = arr.length;
7    this.tree = new Array(this.n + 1).fill(0);
8    
9    // Build Fenwick tree
10    for (let i = 0; i < this.n; i++) {

When to Use Which?

Use Segment Tree When:

• Need range min/max queries (not just sum)
• Need custom aggregate functions (gcd, lcm, etc.)
• Need range updates (lazy propagation)
• Flexibility is more important than simplicity

Use Fenwick Tree When:

• Only need range sum queries
• Space is a concern (Fenwick uses less space)
• Simplicity is important
• Point updates are sufficient

Use Prefix Sums When:

• Array is static (no updates)
• Only need range sum queries
• Want O(1) query time

Common Pitfalls

1. Off-by-one errors: Segment trees use 0-indexed arrays, Fenwick trees use 1-indexed internally
2. Incorrect range handling: Not handling partial overlaps correctly in segment trees
3. Lazy propagation bugs: Incorrectly propagating lazy values in range updates
4. Space allocation: Not allocating enough space (segment trees need 4n, Fenwick needs n+1)
5. Query bounds: Not validating query bounds before processing

Failure Stories You'll Recognize

A game engine was tracking player scores in real-time. It needed to answer "what's the total score of players ranked 100-200?" The system used a sorted array and scanned the range (O(n)). With thousands of queries per second, this became a bottleneck. The fix? Use a Fenwick tree. Range sum queries became O(log n), making leaderboard updates fast enough for real-time gameplay.

Another story: A time-series database was storing sensor readings. Queries like "average temperature from 2 PM to 5 PM" required scanning all readings in that range (O(n)). The fix? Use a segment tree that stores both sum and count. Range average queries became O(log n), dramatically improving query performance.

What Interviewers Are Really Testing

• Advanced algorithms: Can you implement complex tree structures correctly?
• Optimization: Do you understand when these structures are worth the complexity?
• Trade-offs: Can you explain when to use segment trees vs Fenwick trees vs simpler structures?
• Range operations: Do you understand how to efficiently handle range queries and updates?
• Edge cases: Can you handle boundary conditions and off-by-one errors?

Interview Questions

Intermediate

1. Implement a segment tree for range sum queries with point updates
2. Implement a Fenwick tree for range sum queries
3. Find the minimum element in a range using a segment tree

Senior

1. Implement lazy propagation for range updates in segment trees
2. Design a segment tree that supports range min, max, and sum queries
3. Optimize a segment tree for 2D range queries
4. Implement a Fenwick tree that supports range updates
5. Compare and contrast segment trees, Fenwick trees, and prefix sums

1. Segment trees are flexible: Support min, max, sum, gcd, and custom functions
2. Fenwick trees are simpler: Easier to implement, less space, but only for sum queries
3. Both provide O(log n) operations: Query and update in logarithmic time
4. Space trade-offs: Segment trees use 4n space, Fenwick trees use n space
5. Use cases: Range queries, time-series data, competitive programming
6. Lazy propagation: Enables efficient range updates in segment trees
7. 1-indexing in Fenwick: Fenwick trees use 1-indexed arrays internally
8. Consider alternatives: Prefix sums for static arrays, simpler structures when possible
9. Recognition is key: Knowing when range queries are the core requirement
10. Implementation complexity: Segment trees are more complex but more powerful

• Trees - Understanding tree structures
• Arrays - Basic array operations
• Recursion - Essential for tree traversal
• Dynamic Programming - Sometimes combined with segment trees