Range Query Structures

🌳 Range Query Structures: The Super-Fast Answer Machine

Imagine you have a magical bookshelf that can instantly tell you the sum of any books you point at!

🎯 The Big Picture

Think of your data like a row of jars filled with candies. Someone keeps asking you:

• “How many candies are in jars 3 to 7?”
• “How many in jars 1 to 5?”

The slow way: Count each jar every single time. 😴

The smart way: Build a special helper structure that remembers answers! 🚀

Today we’ll learn two magical helpers:

1. Segment Tree - A tree that knows everything
2. Binary Indexed Tree (BIT) - A clever shortcut machine

🌲 Segment Tree Fundamentals

What is a Segment Tree?

Imagine you’re the manager of a candy store with 8 jars. Instead of counting jars every time a customer asks, you create a pyramid of helpers.

         [Total: 1-8]           ← Top helper knows EVERYTHING
        /           \
   [Sum 1-4]     [Sum 5-8]      ← These know half each
    /    \        /     \
 [1-2] [3-4]   [5-6]  [7-8]     ← These know pairs
 / \    / \    / \     / \
1   2  3   4  5   6   7   8     ← Actual jars (leaves)

The Magic: Each helper remembers the sum of their children!

Building a Segment Tree

Let’s say we have 4 jars with candies: [3, 1, 4, 2]

int[] arr = {3, 1, 4, 2};
int[] tree = new int[4 * 4]; // 4n size is safe

void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node: just copy the value
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // Build left child
        build(2*node, start, mid);
        // Build right child
        build(2*node+1, mid+1, end);
        // This node = sum of children
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

Visual Result:

        [10]          ← 3+1+4+2 = 10
       /    \
     [4]    [6]       ← (3+1) and (4+2)
     / \    / \
    3   1  4   2      ← Original values

Why Size 4n?

A segment tree for n elements needs at most 4n space. Think of it like buying extra storage boxes — better safe than sorry!

🔍 Segment Tree Range Query

The Question Game

“What’s the sum from jar 1 to jar 3?”

Instead of adding arr[1] + arr[2] + arr[3], we ask our tree helpers!

How Range Query Works

The tree walks down and collects answers:

int query(int node, int start, int end,
          int L, int R) {
    // Case 1: Completely outside
    if (R < start || end < L) {
        return 0; // Contributes nothing
    }
    // Case 2: Completely inside
    if (L <= start && end <= R) {
        return tree[node]; // Use stored sum!
    }
    // Case 3: Partial overlap
    int mid = (start + end) / 2;
    int leftSum = query(2*node, start, mid, L, R);
    int rightSum = query(2*node+1, mid+1, end, L, R);
    return leftSum + rightSum;
}

Example: Query Sum(1, 2)

With array [3, 1, 4, 2] (0-indexed):

Query: L=1, R=2 (sum of positions 1 and 2)

Step 1: Root [0-3] - Partial overlap
Step 2: Left child [0-1] - Partial overlap
        → Position 1 gives us: 1
Step 3: Right child [2-3] - Partial overlap
        → Position 2 gives us: 4

Answer: 1 + 4 = 5 ✓

Time Complexity

For 1 million elements:

• Naive: 1,000,000 operations per query 😰
• Segment Tree: ~20 operations per query 🎉

✏️ Segment Tree Update

The Problem with Change

A customer adds candies to jar 2. Now our tree’s sums are wrong!

Old: [3, 1, 4, 2] → New: [3, 5, 4, 2]

We need to update the tree — but not rebuild everything!

Point Update: The Domino Effect

When one leaf changes, only its ancestors need updating:

void update(int node, int start, int end,
            int idx, int val) {
    if (start == end) {
        // Found the leaf!
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            // Go left
            update(2*node, start, mid, idx, val);
        } else {
            // Go right
            update(2*node+1, mid+1, end, idx, val);
        }
        // Recalculate this node
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

Visual Update Example

Updating position 1 from 1 to 5:

BEFORE:                    AFTER:
      [10]                      [14]  ← 4+10=14
     /    \                    /    \
   [4]    [6]               [8]    [6]  ← 3+5=8
   / \    / \               / \    / \
  3   1  4   2             3   5  4   2  ← Changed!
      ↑                        ↑
   Update this!            Only these 3 nodes changed

Only O(log n) nodes updated! The magic of trees! 🌟

🎋 Binary Indexed Tree (BIT)

A Lighter, Faster Friend

Also called Fenwick Tree, this is a cleverer way to do the same job with less memory and simpler code.

The Secret: Binary Magic

BIT uses a clever trick with binary numbers:

• Position 6 in binary = 110
• The rightmost 1 bit tells us how many elements this position “covers”

Index (decimal) | Binary | Covers
       1        |  0001  | 1 element
       2        |  0010  | 2 elements
       3        |  0011  | 1 element
       4        |  0100  | 4 elements
       5        |  0101  | 1 element
       6        |  0110  | 2 elements
       7        |  0111  | 1 element
       8        |  1000  | 8 elements

The BIT Array

int[] BIT = new int[n + 1]; // 1-indexed!

Each BIT[i] stores the sum of a specific range ending at i.

⚡ BIT Operations

Operation 1: Get Prefix Sum

To find sum from 1 to i, we hop backwards removing the lowest set bit:

int getSum(int i) {
    int sum = 0;
    while (i > 0) {
        sum += BIT[i];
        i -= (i & (-i)); // Remove lowest set bit
    }
    return sum;
}

Example: Sum(1 to 7)

i = 7 (0111) → add BIT[7], then i = 6
i = 6 (0110) → add BIT[6], then i = 4
i = 4 (0100) → add BIT[4], then i = 0
Done! Only 3 steps for 7 elements!

The Magic Formula: i & (-i)

This extracts the lowest set bit:

  7 = 0111
 -7 = 1001 (two's complement)
7&-7= 0001 ← Lowest set bit!

Operation 2: Update Value

When we change a value, we update all BIT positions that include it:

void update(int i, int delta) {
    while (i <= n) {
        BIT[i] += delta;
        i += (i & (-i)); // Add lowest set bit
    }
}

Example: Update position 3

i = 3 (0011) → update BIT[3], then i = 4
i = 4 (0100) → update BIT[4], then i = 8
i = 8 (1000) → update BIT[8], then i = 16
Done! Only 3 updates for an 8-element array!

Range Sum with BIT

To get sum from L to R:

int rangeSum(int L, int R) {
    return getSum(R) - getSum(L - 1);
}

Example: Sum from 3 to 6

= getSum(6) - getSum(2)
= (sum 1-6) - (sum 1-2)
= sum 3-6 ✓

🥊 Segment Tree vs BIT: The Showdown

When to Use What?

• Use BIT when: You only need sum/count queries and updates are point-based
• Use Segment Tree when: You need min/max, range updates, or complex operations

🎨 Complete Working Examples

Full Segment Tree Implementation

class SegmentTree {
    int[] tree, arr;
    int n;

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

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

    int 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];
        int mid = (s + e) / 2;
        return 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 i, int v) {
        if (s == e) {
            arr[i] = v;
            tree[node] = v;
            return;
        }
        int mid = (s + e) / 2;
        if (i <= mid) update(2*node, s, mid, i, v);
        else update(2*node+1, mid+1, e, i, v);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

Full BIT Implementation

class BIT {
    int[] tree;
    int n;

    BIT(int size) {
        n = size;
        tree = new int[n + 1];
    }

    void update(int i, int delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }

    int rangeQuery(int L, int R) {
        return query(R) - query(L - 1);
    }
}

🧠 Quick Memory Tricks

graph TD
    A["Need Range Queries?"] -->|Yes| B{What operation?}
    B -->|Sum/Count only| C["Use BIT - Simpler!"]
    B -->|Min/Max/Complex| D["Use Segment Tree"]
    A -->|No| E["Use simple array"]

Remember This Rhyme:

"BIT for sums, quick and light, Segment Tree for everything — day or night!"

🎯 Key Takeaways

1. Segment Tree = Tree that pre-computes answers for all possible ranges
2. Build once O(n), query forever O(log n)
3. BIT = Clever use of binary numbers for prefix sums
4. i & (-i) = Magic formula for the lowest set bit
5. Both turn O(n) queries into O(log n) ⚡

You’ve just learned the secret weapons of competitive programmers! 🏆

Now go build some super-fast query machines! 🚀