Dynamic Lazy Segment Tree (ds/dynlazysegtree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-18 22:02:23+07:00
• Include: #include "ds/dynlazysegtree.hpp"

Description

Dynamic lazy segment tree is a space-efficient lazy segment tree that only allocates nodes when needed. It can handle range queries with range updates under a monoid in $\mathcal O(\log n)$ time per operation, using $\mathcal O(q \log n)$ space where $q$ is the number of operations. This is useful when the coordinate space is large but only a few indices are accessed.

Example monoid:

struct RangeAffineRangeSum {
  using T = array<int, 2>;
  using F = array<int, 2>;
  static T id() { return {0, 0}; }
  static F fid() { return {1, 0}; }
  static T op(T l, T r) { return {l[0] + r[0], l[1] + r[1]}; }
  // l is applied later than r
  static F comp(F l, F r) { return {l[0] * r[0], l[0] * r[1] + l[1]}; }
  static T map(F f, T x, I tl, I tr) {
    return {x[0] * f[0] + x[1] * f[1], x[1]};
  }
};

Operations

• DynLazySegTree<M, I>(I n)
  • Construct dynamic lazy segment tree with coordinate space [0, n)
  • Time complexity: $\mathcal O(1)$
• T operator()(I l, I r) or T prod(I l, I r)
  • Returns the product of the range [l, r)
  • Time complexity: $\mathcal O(\log n)$
• void apply(I l, I r, F f)
  • Applies update f to the range [l, r)
  • Time complexity: $\mathcal O(\log n)$
• I max_right(I l, G g)
  • Finds the maximum r such that g(prod(l, r)) == true. For requirements of g, please visit ac-library’s segtree docs
  • Time complexity: $\mathcal O(\log n)$

Depends on

• other/st_alloc.hpp

Verified with

• test/yosupo/ds/segment_tree/range_affine_range_sum_large_array.test.cpp

Code

#pragma once

#include "../other/st_alloc.hpp"

template<class M, class I = int> struct DynLazySegTree {
    using T = typename M::T;
    using F = typename M::F;

    struct node;
    using ptr = node *;
    struct node : st_alloc<node> {
        ptr l = 0, r = 0;
        T x = M::id();
        F lz = M::fid();

        node() {}

        ptr ch(bool z) {
            auto &c = !z ? l : r;
            return c = c ?: new node();
        }
    };

    I n;
    ptr root = 0;

    DynLazySegTree() {}
    DynLazySegTree(I _n) : n(_n), root(new node()) {}

    T operator()(I l, I r) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return M::id();
            if (l <= tl && tr <= r) return t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) return self(self, t->l, tl, tm);
            if (tm <= l) return self(self, t->r, tm, tr);
            return M::op(self(self, t->l, tl, tm), self(self, t->r, tm, tr));
        };
        return rec(rec, root, 0, n);
    }
    void apply(I l, I r, const F &f) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return;
            if (l <= tl && tr <= r) return all_apply(t, f, tl, tr);
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) {
                self(self, t->l, tl, tm);
            } else if (tm <= l) {
                self(self, t->r, tm, tr);
            } else {
                self(self, t->l, tl, tm), self(self, t->r, tm, tr);
            }
            update(t);
        };
        rec(rec, root, 0, n);
    }
    template<class G> I max_right(I l, G &&g) const {
        assert(0 <= l && l <= n);
        assert(g(M::id()));
        if (l == n) return n;
        I r = l;
        T sm = M::id();
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (tr - tl == 1) return r = g(M::op(sm, t->x)) ? tr : tl, t->x;
            if (l <= tl && g(M::op(sm, t->x))) return r = tr, t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (tm <= l) return self(self, t->r, tm, tr);
            auto lx = self(self, t->l, tl, tm);
            if (!g(M::op(sm, lx))) return lx;
            sm = M::op(sm, lx);
            return self(self, t->r, tm, tr);
        };
        rec(rec, root, 0, n);
        return r;
    }

  private:
    static void update(ptr t) { t->x = M::op(t->l->x, t->r->x); }
    static void all_apply(ptr t, const F &f, I tl, I tr) {
        t->x = M::map(f, t->x, tl, tr);
        t->lz = M::comp(f, t->lz);
    }
    static void push(ptr t, I tl, I tr) {
        I tm = (tl + tr) / 2;
        all_apply(t->ch(0), t->lz, tl, tm);
        all_apply(t->ch(1), t->lz, tm, tr);
        t->lz = M::fid();
    }
};

#line 2 "ds/dynlazysegtree.hpp"

#line 2 "other/st_alloc.hpp"

template<class T> struct st_alloc {
    static inline stack<T> pool;
    void *operator new(size_t) { return pool.emplace(), &pool.top(); }
    void operator delete(void *) {}
};
#line 4 "ds/dynlazysegtree.hpp"

template<class M, class I = int> struct DynLazySegTree {
    using T = typename M::T;
    using F = typename M::F;

    struct node;
    using ptr = node *;
    struct node : st_alloc<node> {
        ptr l = 0, r = 0;
        T x = M::id();
        F lz = M::fid();

        node() {}

        ptr ch(bool z) {
            auto &c = !z ? l : r;
            return c = c ?: new node();
        }
    };

    I n;
    ptr root = 0;

    DynLazySegTree() {}
    DynLazySegTree(I _n) : n(_n), root(new node()) {}

    T operator()(I l, I r) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return M::id();
            if (l <= tl && tr <= r) return t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) return self(self, t->l, tl, tm);
            if (tm <= l) return self(self, t->r, tm, tr);
            return M::op(self(self, t->l, tl, tm), self(self, t->r, tm, tr));
        };
        return rec(rec, root, 0, n);
    }
    void apply(I l, I r, const F &f) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return;
            if (l <= tl && tr <= r) return all_apply(t, f, tl, tr);
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) {
                self(self, t->l, tl, tm);
            } else if (tm <= l) {
                self(self, t->r, tm, tr);
            } else {
                self(self, t->l, tl, tm), self(self, t->r, tm, tr);
            }
            update(t);
        };
        rec(rec, root, 0, n);
    }
    template<class G> I max_right(I l, G &&g) const {
        assert(0 <= l && l <= n);
        assert(g(M::id()));
        if (l == n) return n;
        I r = l;
        T sm = M::id();
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (tr - tl == 1) return r = g(M::op(sm, t->x)) ? tr : tl, t->x;
            if (l <= tl && g(M::op(sm, t->x))) return r = tr, t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (tm <= l) return self(self, t->r, tm, tr);
            auto lx = self(self, t->l, tl, tm);
            if (!g(M::op(sm, lx))) return lx;
            sm = M::op(sm, lx);
            return self(self, t->r, tm, tr);
        };
        rec(rec, root, 0, n);
        return r;
    }

  private:
    static void update(ptr t) { t->x = M::op(t->l->x, t->r->x); }
    static void all_apply(ptr t, const F &f, I tl, I tr) {
        t->x = M::map(f, t->x, tl, tr);
        t->lz = M::comp(f, t->lz);
    }
    static void push(ptr t, I tl, I tr) {
        I tm = (tl + tr) / 2;
        all_apply(t->ch(0), t->lz, tl, tm);
        all_apply(t->ch(1), t->lz, tm, tr);
        t->lz = M::fid();
    }
};

Back to top page