guest@itl:~/home/data-structures$
templates/lazy-segment-tree.cpp
compilable
$cat templates/lazy-segment-tree

Lazy Segment Tree

Segment tree with lazy propagation — supports range updates and range queries in O(log n).

[Data Structures]|
Jul 9, 2026
|explanatory_notes.md|
#segment-tree#lazy-propagation#range-update#range-query
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5;
ll tree[4 * MAXN], lazy[4 * MAXN];
ll IDENTITY = 0, LAZY_ID = 0;
int n;

ll combine(ll a, ll b) { return a + b; }
ll apply(ll val, ll lz, int len) { return val + lz * len; }
ll compose(ll old_lz, ll new_lz) { return old_lz + new_lz; }

void pushDown(int idx, int lx, int rx) {
    if (lazy[idx] == LAZY_ID) return;
    int mid = (lx + rx) / 2;
    tree[2 * idx] = apply(tree[2 * idx], lazy[idx], mid - lx + 1);
    lazy[2 * idx] = compose(lazy[2 * idx], lazy[idx]);
    tree[2 * idx + 1] = apply(tree[2 * idx + 1], lazy[idx], rx - mid);
    lazy[2 * idx + 1] = compose(lazy[2 * idx + 1], lazy[idx]);
    lazy[idx] = LAZY_ID;
}

void build(ll a[], int idx, int lx, int rx) {
    if (lx == rx) { tree[idx] = a[lx]; return; }
    int mid = (lx + rx) / 2;
    build(a, 2 * idx, lx, mid);
    build(a, 2 * idx + 1, mid + 1, rx);
    tree[idx] = combine(tree[2 * idx], tree[2 * idx + 1]);
}

void build(ll a[]) { build(a, 1, 1, n); }

void update(int l, int r, ll val, int idx, int lx, int rx) {
    if (lx > r || rx < l) return;
    if (lx >= l && rx <= r) {
        tree[idx] = apply(tree[idx], val, rx - lx + 1);
        lazy[idx] = compose(lazy[idx], val);
        return;
    }
    pushDown(idx, lx, rx);
    int mid = (lx + rx) / 2;
    update(l, r, val, 2 * idx, lx, mid);
    update(l, r, val, 2 * idx + 1, mid + 1, rx);
    tree[idx] = combine(tree[2 * idx], tree[2 * idx + 1]);
}

void update(int l, int r, ll val) { update(l, r, val, 1, 1, n); }

ll query(int l, int r, int idx, int lx, int rx) {
    if (lx > r || rx < l) return IDENTITY;
    if (lx >= l && rx <= r) return tree[idx];
    pushDown(idx, lx, rx);
    int mid = (lx + rx) / 2;
    return combine(query(l, r, 2 * idx, lx, mid),
                   query(l, r, 2 * idx + 1, mid + 1, rx));
}

ll query(int l, int r) { return query(l, r, 1, 1, n); }
59 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Lazy Segment Tree

Extends segment tree to handle range updates by deferring work. Each node stores both a value and a lazy tag.

How It Works

  • Range update — if update covers entire node, apply and store lazy tag

  • Push-down — before accessing children, propagate parent's lazy tag downward

  • Three customizable functions control behavior:

    • - combine(a, b) — merge two children
    - apply(val, lz, len) — apply lazy to node value
    - compose(old, new) — merge two lazy tags

    Common Variants

  • Range add + range sum: combine = a + b, apply = val + lz * len, compose = old + new

  • Range assign + range min: combine = min(a, b), apply = lz, compose = new

  • Range add + range max: combine = max(a, b), apply = val + lz, compose = old + new

    • When to Use

  • Range updates with range queries

  • Problems where updates are additive, multiplicative, or assignment-based

    • Complexity

  • Build — O(n)O(n)

  • Update / Query — O(log⁡n)O(\log n)

  • Space — O(4n)O(4n)