Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Segment tree - Preparation to IOI Part 4

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 4/Module 3: Segment Tree/Segment tree

Segment tree

Segment tree

A segment tree (Segment Tree) is a data structure for quickly answering queries on a subsegment of an array and updating elements.

Usually used for queries like:

sum on a segment $[l, r]$
minimum / maximum on a segment
and other associative operations

Idea

There is an array $a[1..n]$ .

We build a binary tree where:

each node stores a value for some segment $[l, r]$
the root stores the value for the entire array $[1, n]$

Up next

Maximum subarray sum on a given segment

Maximum subarray sum on a given segment

[

1

,

n

]

the left child stores

[l, m]

, the right —

[m+1, r]

, where

m = \lfloor (l+r)/2 \rfloor

For sum:

if a node stores $[l, r]$ , then $t[x] = \sum_{i=l}^{r} a[i]$
then $t[x] = t[2x] + t[2x+1]$

Operations

1) Build (construction)

Recursively:

if $l = r$ , this is a leaf, set $t[x] = a[l]$
otherwise build the children and add

Complexity: $O(n)$

2) Update (updating one element)

Update $a[i] = y$ :

go down the tree to the leaf with index $i$
update the leaf
on the way back recalculate the sums

Complexity: $O(\log n)$

3) Query / Get (sum on a segment)

Find the sum on $[tl, tr]$ :

if the query is empty ( $tl > tr$ ) → $0$
if the current node exactly matches the query → return $t[x]$
otherwise split the query into two parts relative to the middle and sum the results

Complexity: $O(\log n)$ (on average/usually), upper bound $O(\log n)$ for a standard sum-segtree

Memory

Usually the tree is stored in an array of size about $4n$ :

this is enough to fully store all nodes.

Implementation

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n;
int a[N];
long long t[4 * N];

void build(int x, int l, int r) {
    if (l == r) {
        t[x] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(x * 2, l, m);
    build(x * 2 + 1, m + 1, r);
    t[x] = t[x * 2] + t[x * 2 + 1];
}

void upd(int x, int l, int r, int i, int y) {
    if (l == r) {
        t[x] = y;
        return;
    }
    int m = (l + r) / 2;
    if (i <= m) {
        upd(x * 2, l, m, i, y);
    } else {
        upd(x * 2 + 1, m + 1, r, i, y);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
}

long long get(int x, int l, int r, int tl, int tr) {
    if (tl > tr) {
        return 0;
    } else if (l == tl && r == tr) {
        return t[x];
    }
    int m = (l + r) / 2;
    return get(x * 2, l, m, tl, min(m, tr)) + get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr);
}

int main() {
    
    n = 5;
    a[1] = 1;
    a[2] = 1;
    a[3] = 4;
    a[4] = 2;
    a[5] = 3;
    
    build(1, 1, n);
    upd(1, 1, n, 2, 10);
    cout << get(1, 1, n, 1, 4) << "\n";
    
    return 0;
}