What is Segment Tree?

A Segment Tree is a binary tree data structure used to efficiently perform range queries and range updates on an array.

• Efficient querying of intervals/range
• Efficient updating of intervals/range

Problem

      +-----+-----+-----+-----+-----+-----+-----+
arr = |  3  |  1  |  2  |  7  |  5  |  6  |  3  |
      +-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6

Suppose we are given this arr,
and we are asked to find out the sum from index 1 to 4.
sum of index(1, 4)?

Brute Froce Strategy:
We can say that's easy, we can just iterate over the arr
starting from index 1 to 4 adding all the elements.

Now, we are asked another question to find out the sum
from index 2 to 5.

We say no problem, we can again iterate over that range and
hand over the sum.

Now, again we are asked to find out the sum from index 0 to 5.

We can again do the same.

As mentioned in the above problem, we can be given any amount of queries to find out the sum of the range, suppose we are given q number of queries.

Total Queries = q
Length of the arr = n

As we are asked queries again and again, doing we iterate over the array from
start index of the range to end index of the range.

In the worst case, time complexity would be = O(q*n)

What if n is huge number, let n be 10^6
and q = 10^4
Time Complexity would be = O(10^4 * 10^6) = O(10^10)

Modern computers can perform around 10^8 operations per second.

So:

• O(10^10) operations would take ~ 100 seconds or more – too slow for online judges.

This is where Segment Tree comes to the rescue.

The problem involving range queries to find:

• Sum
• Minimum
• Maximum
• XOR
• GCD/LCM
• Count
• Modulo
• Product

Especially when the array is large, this is where Segment Trees is used.

How to Build Segment Tree?

Suppose we are given an array arr:

      +-----+-----+-----+-----+-----+
arr = |  3  |  1  |  2  |  7  |  1  |
      +-----+-----+-----+-----+-----+
         0     1     2     3     4
n (length of the array) = 5

2️⃣ Update Query

Suppose:

You have an array:

nums = [1, 3, 5, 7, 9]
prefix = [1, 4, 9, 16, 25]  // prefix[i] = sum(nums[0..i])

Now let's say you update nums[1] = 10

Now nums becomes:

nums = [1, 10, 5, 7, 9]

What Happens to prefix[]?

You need to recalculate all elements from index 1 to the end:

prefix[1] = prefix[0] + nums[1] = 1 + 10 = 11
prefix[2] = prefix[1] + nums[2] = 11 + 5 = 16
prefix[3] = prefix[2] + nums[3] = 16 + 7 = 23
prefix[4] = prefix[3] + nums[4] = 23 + 9 = 32

So, just one update to nums[1] cause O(n) time to recompute the prefix array.

In a segment tree, an update to nums[i]:

• Only affects the logarithmic number of nodes
• Takes O(log n) time
• Other ranges remain unaffected