Algoritmalar
en

Segment Tree

Trees O(log n) query O(n)

A binary tree over array ranges: each node stores an aggregate (here, a sum) so range queries resolve in O(log n) by combining O(log n) covering nodes.

37[0,7]12[0,3]7[0,1]2[0]5[1]5[2,3]1[2]4[3]25[4,7]12[4,5]9[4]3[5]13[6,7]7[6]6[7]
input array
20
51
12
43
94
35
76
67
1/24

Leaf [0] = 2.

InvariantEach node stores the sum of its range, so any query is a handful of whole ranges rather than a scan.

segment-tree.c
int tree[4 * MAXN];
 
void build(int a[], int node, int lo, int hi) {
    if (lo == hi) {
        tree[node] = a[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    build(a, 2*node, lo, mid);
    build(a, 2*node+1, mid+1, hi);
    tree[node] = tree[2*node] + tree[2*node+1];
}
 
int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return tree[node];
    int mid = (lo + hi) / 2;
    return query(2*node, lo, mid, l, r)
         + query(2*node+1, mid+1, hi, l, r);
}

How Segment Tree works

Each node stores an aggregate of an array range; children split the range in half. A query stitches its answer from O(log n) disjoint covering nodes; an update refreshes one leaf-to-root path.

When to use it

Range queries (sum/min/max) interleaved with point updates: competitive programming, analytics windows.