# Segment Tree — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/segment-tree

> A binary tree over an array that answers range queries (sum, min, max) and point updates in O(log n).

## Why not brute force?

A naive range-sum query scans the whole range — `O(n)` per query. A **segment tree** precomputes sums over halves recursively, so any range query becomes `O(log n)`. Each node stores the aggregate of a sub-range; leaves are single elements.

## Build & query

Store the tree in an array of size `4n`. `build` fills bottom-up, `query` recurses only into overlapping halves.

```python
tree = [0] * (4 * n)

def build(node, lo, hi):
    if lo == hi:
        tree[node] = arr[lo]
        return
    mid = (lo + hi) // 2
    build(2*node, lo, mid)
    build(2*node+1, mid+1, hi)
    tree[node] = tree[2*node] + tree[2*node+1]

def query(node, lo, hi, l, r):
    if r < lo or hi < l:
        return 0
    if l <= lo and hi <= r:
        return tree[node]
    mid = (lo + hi) // 2
    return query(2*node, lo, mid, l, r) + query(2*node+1, mid+1, hi, l, r)
```

Output:

```
build(1, 0, n-1)
query(1, 0, n-1, 2, 5)  # sum of arr[2..5]
```

## Point update

Updating one element only touches the `O(log n)` nodes on the path from root to that leaf, then fixes sums on the way back up.

```python
def update(node, lo, hi, idx, val):
    if lo == hi:
        tree[node] = val
        return
    mid = (lo + hi) // 2
    if idx <= mid:
        update(2*node, lo, mid, idx, val)
    else:
        update(2*node+1, mid+1, hi, idx, val)
    tree[node] = tree[2*node] + tree[2*node+1]
```

## When to reach for it

Use a segment tree when you need **many range queries interleaved with updates** — range-sum, range-min/max, or even range-GCD. If updates never happen, a simple **prefix-sum array** is `O(1)` per query and simpler.