How Segment Trees Enable Lightning‑Fast Range Sum Queries

Segment Tree Overview

Segment tree is a binary‑tree data structure for dynamic interval problems, supporting range queries and point updates efficiently.

Construction (Iterative Bottom‑Up)

Given array arr = [10, 20, 30, 40, 50, 60, 70, 80], leaf nodes store the elements. Adjacent leaves are summed to form parent nodes, repeated until a single root node holds the total sum 360.

360
       /   \
     100   260
    / \   / \
   30 70 110 150
  / \ / \ / \ / \
10 20 30 40 50 60 70 80

Index Structure and Node Numbering

Intervals are derived by binary splitting of the index range [0,7]:

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

Each node stores the sum of its interval, e.g., node [0,3] stores arr[0]+…+arr[3].

Why Queries Are Fast

Scanning a 60 000‑element array for a range sum is O(n). A segment tree visits only O(log n) relevant nodes.

Example: to compute sum(arr[1:6]) = 20+30+40+50+60+70, the visited nodes are tree[9]=20, tree[5]=70, tree[6]=110, tree[14]=70. Adding them yields the result.

Node Numbering and Query Procedure

Root node is numbered 1.

For any node x, parent = x/2, left child = 2*x, right child = 2*x+1.

Iterative Query Algorithm (range sum)

Initialize left = 9, right = 14, result = 0.

While left <= right:

If left is odd, add tree[left] to result and increment left.

If right is even, add tree[right] to result and decrement right.

Then set left //= 2, right //= 2 and repeat.

When left > right, return result.

Iterative Implementation (Python)

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query_r_open(self, left, right):  # left‑closed, right‑open
        result = 0
        left += self.n
        right += self.n
        while left < right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                result += self.tree[right]
            left //= 2
            right //= 2
        return result

    def query_r_close(self, left, right):  # left‑closed, right‑closed
        result = 0
        left += self.n
        right += self.n
        while left <= right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1
            if right % 2 == 0:
                result += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
        return result

    def update(self, index, value):
        index += self.n
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

arr = [10,20,30,40,50,60,70,80]
seg = SegmentTree(arr)
print(seg.tree[:])                # initial tree
print(seg.query_r_open(1,7))     # [1,7) → 270
print(seg.query_r_close(1,7))    # [1,7] → 350
seg.update(1,90)                  # set arr[1]=90
print(seg.tree[:])                # tree after update
print(seg.query_r_open(1,7))     # 340
print(seg.query_r_close(1,7))    # 420

Recursive Construction and Operations

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        left = 2 * node
        right = 2 * node + 1
        self.build(arr, left, start, mid)
        self.build(arr, right, mid + 1, end)
        self.tree[node] = self.tree[left] + self.tree[right]

    def update(self, index, value, node=1, start=0, end=None):
        if end is None:
            end = self.n - 1
        if start == end:
            self.tree[node] = value
            return
        mid = (start + end) // 2
        if index <= mid:
            self.update(index, value, 2 * node, start, mid)
        else:
            self.update(index, value, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, left, right, node=1, start=0, end=None):
        if end is None:
            end = self.n - 1
        if right < start or left > end:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        return (self.query(left, right, 2 * node, start, mid) +
                self.query(left, right, 2 * node + 1, mid + 1, end))

arr = [1,3,5,7,9,11]
seg = SegmentTree(arr)
print(seg.query(1,3))   # 15
seg.update(2,10)
print(seg.query(1,3))   # 20

The recursive version uses a 4 n array, explicit build, update, and query functions. Query handling distinguishes three cases: no overlap (return 0), total overlap (return node value), partial overlap (recurse left and right).

Advantages

Range‑sum queries and point updates in O(log n) time.

Construction time O(n) and space O(n) for the iterative version (2 n) or O(4 n) for the recursive version.

When only small ranges are queried, a simple array scan may be faster.