Range Query Structures

Range Query Structures: Your Super-Fast Answer Machine! 🚀

Imagine you have a giant bookshelf with thousands of books. Each book has a number on its spine. Now, your friend asks: “What’s the total of all numbers from book 50 to book 200?”

Would you count one by one? That would take forever! 😩

What if you had a magical helper who already knew the answers to common questions? That’s exactly what Range Query Structures do!

🌳 The Magic Tree: Segment Tree Fundamentals

What is a Segment Tree?

Think of a Segment Tree like a family tree, but for numbers!

The Story: You have 8 toy boxes with different numbers of toys:

Boxes: [2, 5, 1, 4, 9, 3, 6, 7]

Instead of counting toys every time, you build a helper tree:

graph TD
    A["Total: 37"] --> B["Left Half: 12"]
    A --> C["Right Half: 25"]
    B --> D["2+5=7"]
    B --> E["1+4=5"]
    C --> F["9+3=12"]
    C --> G["6+7=13"]
    D --> H["2"]
    D --> I["5"]
    E --> J["1"]
    E --> K["4"]
    F --> L["9"]
    F --> M["3"]
    G --> N["6"]
    G --> O["7"]

How It Works

Bottom Level: Your actual numbers (the toy boxes) Middle Levels: Groups of answers already calculated Top Level: The answer for EVERYTHING!

Building the Tree

// Our toy boxes
let boxes = [2, 5, 1, 4, 9, 3, 6, 7];

// Tree needs 2n-1 space
let tree = new Array(2 * 8 - 1);

// Build from leaves up!
function buildTree(arr, tree, node,
                   start, end) {
  if (start === end) {
    // Leaf: just the number itself
    tree[node] = arr[start];
  } else {
    let mid = Math.floor(
      (start + end) / 2
    );
    let leftChild = 2 * node + 1;
    let rightChild = 2 * node + 2;

    // Build left and right
    buildTree(arr, tree, leftChild,
              start, mid);
    buildTree(arr, tree, rightChild,
              mid + 1, end);

    // Parent = sum of children
    tree[node] = tree[leftChild] +
                 tree[rightChild];
  }
}

Why is this magical?

• Building takes O(n) time (do it once!)
• Tree has about 2n nodes
• Each parent knows the sum of its children

🔍 Segment Tree Range Query: Ask Your Magic Tree!

Now the fun part! Let’s ask the tree questions!

The Question Game

You ask: “What’s the sum from box 2 to box 5?” The tree thinks: “Let me check my notes…”

graph TD
    A["🔍 Need: boxes 2-5"] --> B["Check left: 0-3"]
    A --> C["Check right: 4-7"]
    B --> D["Partial match!<br/>Take boxes 2-3"]
    C --> E["Partial match!<br/>Take boxes 4-5"]
    D --> F["Answer: 1+4=5"]
    E --> G["Answer: 9+3=12"]
    F --> H["Final: 5+12=17 ✅"]
    G --> H

Three Magic Rules

When the tree looks at each node:

The Query Code

function query(tree, node, start, end,
               left, right) {
  // Rule 1: No overlap
  if (right < start || left > end) {
    return 0;
  }

  // Rule 2: Complete overlap
  if (left <= start && end <= right) {
    return tree[node];
  }

  // Rule 3: Partial - ask children
  let mid = Math.floor(
    (start + end) / 2
  );
  let leftSum = query(
    tree, 2*node+1, start, mid,
    left, right
  );
  let rightSum = query(
    tree, 2*node+2, mid+1, end,
    left, right
  );

  return leftSum + rightSum;
}

// Ask: sum of boxes 2 to 5
let answer = query(tree, 0, 0, 7, 2, 5);
// Answer: 17 (1+4+9+3)

Why So Fast?

• Only visits O(log n) nodes!
• 8 boxes? Check ~3 nodes
• 1,000,000 boxes? Check ~20 nodes!

✏️ Segment Tree Update: Change a Box!

What if you add more toys to box 3?

The Ripple Effect

When you change one box, you need to update all the parents above it!

graph TD
    A["Update total!"] --> B["Update this half"]
    B --> E["Update this quarter"]
    E --> K["Box 3: 4→10"]
    style K fill:#ffcc00
    style E fill:#ffdd55
    style B fill:#ffee88
    style A fill:#ffffaa

Update Code

function update(tree, node, start, end,
                idx, newValue) {
  if (start === end) {
    // Found the box!
    tree[node] = newValue;
  } else {
    let mid = Math.floor(
      (start + end) / 2
    );

    if (idx <= mid) {
      // Go left
      update(tree, 2*node+1, start, mid,
             idx, newValue);
    } else {
      // Go right
      update(tree, 2*node+2, mid+1, end,
             idx, newValue);
    }

    // Update this node too!
    tree[node] = tree[2*node+1] +
                 tree[2*node+2];
  }
}

// Change box 3 from 4 to 10
update(tree, 0, 0, 7, 3, 10);

Speed Check

🌲 Binary Indexed Tree: The Clever Cousin

Meet the Binary Indexed Tree (also called Fenwick Tree)!

It’s like a Segment Tree’s clever cousin who uses a cool number trick to be even simpler!

The Binary Magic

Here’s the secret: computers use binary numbers (0s and 1s).

Index 6 in binary = 110
Index 7 in binary = 111
Index 8 in binary = 1000

How BIT Stores Data

Each position stores a special sum:

Position 1: just box[1]
Position 2: box[1] + box[2]
Position 3: just box[3]
Position 4: box[1]+box[2]+box[3]+box[4]
Position 5: just box[5]
Position 6: box[5] + box[6]
Position 7: just box[7]
Position 8: all 8 boxes!

graph TD
    A["BIT[8] covers 1-8"] --> B["BIT[4] covers 1-4"]
    A --> C["BIT[6] covers 5-6"]
    A --> D["BIT[7] covers 7"]
    B --> E["BIT[2] covers 1-2"]
    B --> F["BIT[3] covers 3"]
    E --> G["BIT[1] covers 1"]

The Pattern

Look at the rightmost 1-bit:

• Position 4 (100) → covers 4 numbers
• Position 6 (110) → covers 2 numbers
• Position 7 (111) → covers 1 number

⚙️ BIT Operations: The Number Dance

Finding the Lowest Bit

The magic formula to find the rightmost 1:

function lowbit(x) {
  return x & (-x);
}

// Examples:
lowbit(6);  // 6=110 → returns 2 (10)
lowbit(8);  // 8=1000 → returns 8
lowbit(12); // 12=1100 → returns 4

Prefix Sum Query

To find sum from 1 to i, we “hop” backwards:

function prefixSum(BIT, i) {
  let sum = 0;
  while (i > 0) {
    sum += BIT[i];
    i -= lowbit(i);  // Remove last 1-bit
  }
  return sum;
}

// Sum from 1 to 7:
// Start: i=7 (111)
// Add BIT[7], i becomes 6 (110)
// Add BIT[6], i becomes 4 (100)
// Add BIT[4], i becomes 0
// Done! Only 3 hops!

Range Sum

Want sum from L to R?

function rangeSum(BIT, L, R) {
  return prefixSum(BIT, R) -
         prefixSum(BIT, L - 1);
}

// Sum from 3 to 7:
// = prefixSum(7) - prefixSum(2)

Update Operation

When you change a value, hop forward:

function update(BIT, i, delta, n) {
  while (i <= n) {
    BIT[i] += delta;
    i += lowbit(i);  // Add last 1-bit
  }
}

// Update position 3 by adding 5:
// Start: i=3 (011)
// Update BIT[3], i becomes 4 (100)
// Update BIT[4], i becomes 8 (1000)
// Update BIT[8], i becomes 16 (stop)

Complete BIT Example

class BinaryIndexedTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  lowbit(x) {
    return x & (-x);
  }

  update(i, delta) {
    while (i <= this.n) {
      this.tree[i] += delta;
      i += this.lowbit(i);
    }
  }

  prefixSum(i) {
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= this.lowbit(i);
    }
    return sum;
  }

  rangeSum(L, R) {
    return this.prefixSum(R) -
           this.prefixSum(L - 1);
  }
}

// Use it!
let bit = new BinaryIndexedTree(8);
// Add values
bit.update(1, 2);
bit.update(2, 5);
bit.update(3, 1);
// Query range 1 to 3
bit.rangeSum(1, 3); // Returns 8

🥊 Segment Tree vs Binary Indexed Tree

When to Use What?

• BIT: Simple sum/count queries, cleaner code
• Segment Tree: Complex queries (min, max, GCD), range updates

🎯 Quick Summary

Segment Tree:

• Tree where parents store combined answers
• Query any range in O(log n)
• Update one element in O(log n)

Binary Indexed Tree:

• Uses binary number tricks
• Simpler code, less memory
• Perfect for cumulative sums

🌟 You Did It!

You’ve learned two powerful tools that turn slow O(n) operations into lightning-fast O(log n) operations!

Remember:

• When you need fast range answers → Use these structures!
• Segment Tree = More flexible
• BIT = Simpler and smaller

Now you have superpowers for handling big data! 🦸‍♂️