🏠/Guides/Dsa Prep/Topic Guides/Segment Tree
On this page

Segment Tree

Segment Tree & Fenwick Tree

1. Fenwick Tree (Binary Indexed Tree)

Good for: point updates, prefix queries. Not good for: range updates (without extra BIT), non-invertible functions.

type BIT struct { tree []int }

func NewBIT(n int) *BIT {
    return &BIT{make([]int, n+1)}
}

func (b *BIT) Add(idx, delta int) {
    for i := idx; i < len(b.tree); i += i & -i {
        b.tree[i] += delta
    }
}

func (b *BIT) Sum(idx int) int {
    res := 0
    for i := idx; i > 0; i -= i & -i {
        res += b.tree[i]
    }
    return res
}

func (b *BIT) RangeSum(l, r int) int {
    return b.Sum(r) - b.Sum(l-1)
}

BIT tricks:

  • Range update, point query: BIT diff array. Add(l, v), Add(r+1, -v). Point query = Sum(idx).
  • Kth order statistic: BIT + binary lifting. Walk down the BIT to find smallest idx where prefix sum ≥ k.
  • Inversion count: Iterate right to left, BIT.query(nums[i]-1) for count of smaller seen.

2. Segment Tree

Use when: range query + point update, need max/min/gcd/any associative operation.

type SegTree struct {
    n    int
    tree []int  // 1-indexed segment tree
}

func NewSegTree(arr []int) *SegTree {
    n := len(arr)
    tree := make([]int, 4*n)
    st := &SegTree{n, tree}
    st.build(arr, 1, 0, n-1)
    return st
}

func (st *SegTree) build(arr []int, node, l, r int) int {
    if l == r { 
        st.tree[node] = arr[l]; return st.tree[node] 
    }
    mid := (l + r) / 2
    left := st.build(arr, node*2, l, mid)
    right := st.build(arr, node*2+1, mid+1, r)
    st.tree[node] = max(left, right)  // or min, sum, gcd
    return st.tree[node]
}

func (st *SegTree) Update(pos, val int) {
    st._update(1, 0, st.n-1, pos, val)
}

func (st *SegTree) _update(node, l, r, pos, val int) {
    if l == r {
        st.tree[node] = val
        return
    }
    mid := (l + r) / 2
    if pos <= mid {
        st._update(node*2, l, mid, pos, val)
    } else {
        st._update(node*2+1, mid+1, r, pos, val)
    }
    st.tree[node] = max(st.tree[node*2], st.tree[node*2+1])
}

func (st *SegTree) Query(ql, qr int) int {
    return st._query(1, 0, st.n-1, ql, qr)
}

func (st *SegTree) _query(node, l, r, ql, qr int) int {
    if ql > r || qr < l { return -inf }  // out of range
    if ql <= l && r <= qr { return st.tree[node] }
    mid := (l + r) / 2
    return max(st._query(node*2, l, mid, ql, qr),
               st._query(node*2+1, mid+1, r, ql, qr))
}

Segment Tree Variants:

  • Lazy Propagation — range updates (add v to entire range). Store lazy[node], push before traversing.
  • Merge Sort Tree — each node stores sorted array of its range. Query: count elements > k in range (O(log²n)).
  • Dynamic Segment Tree — only create nodes when needed (use pointers instead of array, for sparse values up to 1e9).

3. Sparse Table (Static Range Queries)

Preprocess O(n log n), query O(1). Only for idempotent operations (min, max, gcd — NOT sum).

type SparseTable struct {
    st [][]int  // st[k][i] = min of range [i, i+2^k-1]
    log []int
}

func NewSparseTable(arr []int) *SparseTable {
    n := len(arr)
    log := make([]int, n+1)
    for i := 2; i <= n; i++ { log[i] = log[i/2] + 1 }
    k := log[n] + 1

    st := make([][]int, k)
    st[0] = arr
    for j := 1; j < k; j++ {
        st[j] = make([]int, n-(1<<j)+1)
        for i := 0; i <= n-(1<<j); i++ {
            st[j][i] = min(st[j-1][i], st[j-1][i+(1<<(j-1))])
        }
    }
    return &SparseTable{st, log}
}

func (sp *SparseTable) Query(l, r int) int {
    j := sp.log[r-l+1]
    return min(sp.st[j][l], sp.st[j][r-(1<<j)+1])
}
← Previous
Graph Tricks
Segment Tree