segment_tree.md

A segment tree is a data structure that helps answer questions about a range of numbers very quickly, while also allowing updates to the numbers.

Think of it like a smart filing system for an array.

Suppose you have this array:

Index: 0 1 2 3 4 5 6 7
Value: 2 1 5 3 4 7 6 8

Imagine someone repeatedly asks:

• What is the sum from index 2 to 6?
• What is the maximum from index 1 to 5?
• Change the value at index 4 to 10.
• Now answer the same questions again.

If you compute the answer by scanning the array every time, it can be slow.

A segment tree stores answers for many ranges in advance.

Step 1: Split the array into halves

Instead of storing only individual numbers, we also store information for larger ranges.

                [0..7]
              /        \
         [0..3]        [4..7]
        /     \        /     \
    [0..1] [2..3]  [4..5] [6..7]
    /  \    /  \    /  \    /  \
 [0][1][2][3][4][5][6][7]

Each node represents a range.

For example:

• [0..7] represents the whole array.
• [0..3] represents the first half.
• [4..7] represents the second half.

Step 2: Store useful information

If we want range sums, each node stores the sum of its range.

Array:
2 1 5 3 4 7 6 8

Leaves:
2 1 5 3 4 7 6 8

Parents:
[0..1] = 2+1 = 3
[2..3] = 5+3 = 8
[4..5] = 4+7 = 11
[6..7] = 6+8 = 14

Next level:
[0..3] = 3+8 = 11
[4..7] = 11+14 = 25

Root:
[0..7] = 11+25 = 36

Now every node already knows the answer for its range.

Step 3: Answer a query

Suppose we want the sum from index 2 to 6.

Instead of checking every number:

5 + 3 + 4 + 7 + 6

the tree jumps to ranges that fit perfectly.

Need [2..6]

Take:
[2..3] = 8
[4..5] = 11
[6..6] = 6

Total:
8 + 11 + 6 = 25

Notice we never looked at every element individually.

Step 4: Update a value

Suppose index 4 changes:

4 -> 10

Only the nodes containing index 4 need updating.

Leaf:
[4] = 10

Update:
[4..5]
[4..7]
[0..7]

Everything else stays the same.

This is much faster than recomputing every range.

Why is it fast?

For an array of size N:

Operation	Normal array	Segment tree
Query a range	O(N)	O(log N)
Update one value	O(1)	O(log N)

Building the tree initially takes O(N).

Intuition

Imagine a company:

CEO
├── Sales
│   ├── Alice
│   └── Bob
└── Engineering
    ├── Carol
    └── Dave

If you want total sales, you don't ask every employee individually.

You ask each department manager, who already knows the total for their department.

A segment tree works the same way:

• Leaves = individual elements.
• Internal nodes = summary (sum, max, min, GCD, etc.) of a range.
• Larger answers are built from smaller answers.

Common uses

Segment trees can answer many kinds of range queries, such as:

• Sum of a range
• Minimum in a range
• Maximum in a range
• Greatest common divisor (GCD)
• Bitwise AND/OR/XOR
• Any operation where you can combine two child results to get the parent's result

One-sentence summary

A segment tree is a binary tree where each node stores information about a contiguous range of an array, allowing range queries and point updates to be performed in O(log N) time instead of O(N).