Segment Tree

A segment tree is a binary tree used for answering range queries and updating values
efficiently.

Think of it as a divide-and-conquer tool:

 Breaks an array into segments (intervals).

 Stores information (like sum, min, max, gcd, etc.) about each segment.
 Allows you to quickly:
o Query a range (e.g., sum of elements from l to r) in O(log n) time.
o Update an element and still keep queries fast in O(log n) time.

Why do we need it?

Without segment trees:

 Sum/Min/Max over a range → O(n) per query.

 Multiple queries + updates → becomes too slow.

With segment trees:

 Build: O(n)
 Query: O(log n)
 Update: O(log n)
Structure:
 Root Node: The topmost node represents the entire list.
 Internal Nodes: These nodes represent segments of the list.
 Leaf Nodes: These are the individual elements of the list.

Each node can be thought of as a box that holds the sum (or other information) of a part of the list.

Real-World Analogies of Segment Tree

 Bookshelf Sections

Think of a long bookshelf with many books. Each shelf can be divided into smaller sections. If you want to know
the total number of pages in a section of books, you could count each book's pages individually, but that takes
time.

Instead, if you already have the total pages counted for each section, you can quickly find the total for any
group of sections.

 Warehouse Inventory:

Imagine a warehouse with many products. If the manager wants to know how many items are in a specific
range of shelves, having a record for each section of shelves allows the manager to quickly add up the counts
from the relevant sections instead of counting each item individually.

Why Use Segment Tree Data Structure?

Segment Trees are useful because they make certain types of problems much easier and faster to solve:

 Efficient Range Queries

Segment Trees allow you to quickly find the sum, minimum, maximum, or other values in a specific range of an
array.

For example, if you need to find the sum of numbers between two positions in a list many times, a Segment
Tree can do this in a fraction of the time it would take using a simple loop.

 Fast Updates

If you need to change the value of an element in the array and then quickly update the results of your range
queries, Segment Trees handle this efficiently. After an update, the tree adjusts itself to reflect the change, so
future queries are still fast.

 Versatility

Segment Trees can be adapted to solve various problems. They can handle different operations like sum,
minimum, maximum, greatest common divisor (GCD), and more. This flexibility makes them a powerful tool in
many scenarios.

 Space Efficiency

Although Segment Trees take more space than a simple array (about 4 times the array size), this is still
manageable and much more space-efficient compared to some other data structures that provide similar
functionality.

How to Build Segment Tree?

1. Choose an Array
Start with an array of numbers. For example, let’s use the array [2, 4, 1, 3, 5].

2. Create the Leaf Nodes

Each leaf node represents a single element of the array. For our example, we will have five leaf nodes.

3. Build Internal Nodes

Combine pairs of leaf nodes to create their parent nodes. Each parent node stores the sum (or other chosen
operation) of its child nodes.

4. Repeat Until the Root is Created

Continue combining nodes until you reach the top of the tree, known as the root node, which represents the
entire array.

Here’s a visual representation of the segment tree for the array [2, 4, 1, 3, 5]:

Building a Segment Tree

We can build recursively:

1. If start == end, store the value from the array.

2. Else:
o Build left child for [start, mid]
o Build right child for [mid+1, end]
o Store the sum (or min/max) of both children in the current node.
Pseudocode:

function buildTree(arr, tree, node, start, end):

if start == end:

# Leaf node: store array value

tree[node] = arr[start]

else:

mid = (start + end) // 2

# Build left child

buildTree(arr, tree, 2*node, start, mid)

# Build right child

buildTree(arr, tree, 2*node + 1, mid+1, end)

# Internal node: sum of children

tree[node] = tree[2*node] + tree[2*node + 1]

Index: 0 1 2 3

Value: 2 5 1 4

Index: 1 2 3 4 5 6 7

Value: 12 7 5 2 5 1 4

Parent–Child Calculation

If we number nodes starting from 1:

 Left child index = 2 * node

 Right child index = 2 * node + 1
 Parent index = node // 2
Segment Tree Operations
 Query Operation

A query operation in a Segment Tree allows you to retrieve information (like the sum, minimum, maximum, etc.)
from a specific range of the array efficiently.

Example:
Let's use our previously built Segment Tree for the array [2, 4, 1, 3, 5] to find the sum of elements from index 1
to 3 (i.e., the range [4, 1, 3]).

1. Start at the Root:

The root node represents the entire range [0, 4].

2. Check Overlap:
 If the range represented by a node completely overlaps with the query range, return the node's value.
 If there is no overlap, return 0 (or a neutral value for other operations).
 If there is partial overlap, recursively check the left and right children.

3. Combine Results:
Combine the results from the left and right children to get the final answer.

 Update Operation

An update operation modifies an element in the array and updates the Segment Tree accordingly.

Example:
Update the element at index 2 (value 1) to 6 in the array [2, 4, 1, 3, 5].

1. Start at the Root:

The root node represents the entire range [0, 4].

2. Traverse to the Leaf:

Move down the tree to find the leaf node corresponding to the index being updated.

3. Update the Leaf:

Update the value of the leaf node.

4. Update Internal Nodes:

Move back up the tree, updating the values of internal nodes to reflect the change.
Updated Segment Tree:

Query function (sum for [L, R]):

function query(node, start, end, L, R):

if R < start or L > end:

return 0 # no overlap

if L <= start and end <= R:

return tree[node] # total overlap

mid = (start + end) // 2

left_sum = query(2*node, start, mid, L, R)

right_sum = query(2*node+1, mid+1, end, L, R)

return left_sum + right_sum

Point Update

function update(node, start, end, idx, val):

if start == end:

# Leaf node: directly update value

tree[node] = val

else:

mid = (start + end) // 2

if idx <= mid:

update(2*node, start, mid, idx, val) # go left

else:

update(2*node + 1, mid+1, end, idx, val) # go right

# After updating child, recalc parent

tree[node] = tree[2*node] + tree[2*node + 1]

lazy propagation