公開日 :
更新日 :

遅延セグメント木（lazy_segtree）

「区間に操作する」と「区間の集計を求める」を、どちらも O(log N) でできるデータ構造。

データ構造更新取得
累積和できない区間和 \( O(1) \)
Fenwick Tree1点に足す \( O(log N) \)区間和 \( O(log N) \)
セグメント木1点更新 \( O(log N) \)区間の集計 \( O(log N) \)
遅延セグメント木区間に操作 \( O(log N) \)区間の集計 \( O(log N) \)
  • 区間を 1 点ずつ更新すると 1 クエリ O(N log N) かかり、間に合わない。
  • 掛け算や代入が入ると、Fenwick Tree の「差分で持つ」工夫も使えない。

→ 区間更新と区間取得が混ざったら遅延セグ木

仕組み：「あとでやる」をメモしておく

各ノードは担当区間 [L, R) の集計値を持つ。区間更新のとき、ノードの担当区間が丸ごと更新範囲に入っていたら、

  1. そのノードの集計値だけをその場で更新する
  2. 子には降りず、「この操作をあとでやってね」というメモ（lazy）を残す

子を本当に見る必要が出たとき（別のクエリでそこより下に降りるとき）に、初めてメモを子に渡す（push / 伝搬）。

apply(2, 8, f) で [0,8) の木を更新する場合

            [0,8)
          /       \
      [0,4)        [4,8)  ← 丸ごと入る：ここで止めて lazy に f をメモ
      /   \
  [0,2)  [2,4)  ← 丸ごと入る：ここで止めて lazy に f をメモ

触るノードは区間取得と同じく O(log N) 個で済む。

AC Library の Lazy Segtree

AC Library – Lazy Segtree のドキュメントはこちら

#include <atcoder/all>
using namespace atcoder;

lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);  // vector<S> から構築
seg.apply(l, r, f);   // [l, r) に操作 f
seg.apply(p, f);      // 1 点 p に操作 f
seg.prod(l, r);       // [l, r) を op でまとめた値
seg.get(p);           // a[p]
seg.set(p, x);        // a[p] = x
seg.all_prod();       // 全体

添字は 0-indexed、区間は半開区間 [l, r)。

自分で定義する部品 (2種類 × 3つ）

部品意味
Sノードが持つ値
op(x, y)2つの区間の値をまとめる
e()op の単位元（空区間の値）
F遅延させる操作
mapping(f, x)操作 f を区間の値 x に適用した結果
composition(f, g)2つの操作の合成。 g をしてから f
id()何もしない操作

アフィン変換とは

「掛けて、足す」変換。
1 次関数 y = ax + b と同じ形。

x → b·x + c

b と c を選ぶと、よく使う操作がすべて表せる。

bc操作
1cc を足す（加算）
b0b 倍する（乗算）
0cc にする（代入）
10何もしない（id())

遅延セグ木と相性がいい理由

  1. 2 回やってもまたアフィン変換になる（合成で閉じている） f(g(x)) = b₁(b₂x + c₂) + c₁ = (b₁b₂)x + (b₁c₂ + c₁) → 何回操作を重ねても (b, c) の 2 つの数でメモできる。
  2. 区間の和を、要素を見ずに更新できる Σ(b·aᵢ + c) = b·(Σaᵢ) + c·(要素数) → 和と長さが分かれば新しい和が計算できる。

例: [1, 2, 3] に x → 2x + 1 → [3, 5, 7]。和は 2·6 + 1·3 = 15 で一致。

S, F, mapping, composition の作り方

ステップ 1：F を決める

操作 1 回分を、何個の数で表せるかを考える。

アフィン変換なら b と c → struct F { mint b, c; };

ステップ 2：S を決める

最初は答えるのに必要な値だけ入れる。

区間和なら → struct S { mint sum; };

ステップ 3 で足りないものが出たら追加すればよい。
最初から完璧に決めなくてよい。

ステップ 3：mapping を書く

「区間全体に F をしたら S はどうなるか」を式にする。

(b·a₁ + c) + … + (b·aₖ + c) = b·(和) + c·k

→ k（区間の長さ）が必要と分かるので、S に len を足す。

struct S { mint sum; int len; };
S mapping(F f, S x) { return {f.b * x.sum + f.c * x.len, x.len}; }

S を変えたら op と e も合わせる。

S op(S x, S y) { return {x.sum + y.sum, x.len + y.len}; }  // 長さも足す
S e() { return {0, 0}; }                                   // 長さ 0 の空区間

mapping は個々の要素を見ずに書けないといけない。
書けないときは S に情報を足すサイン。

mapping で x.len を返す理由

S は {sum, len} の 2 つを持つので、戻り値も 2 つとも決めて返す必要がある。S の各メンバーについて「この操作で変わるか？」を考える。

メンバーアフィン変換で返す値
sum変わるf.b * x.sum + f.c * x.len
len変わらない（要素数は増減しない）x.len

len を省くと 0 になり、次の操作で c·0 となって c が足されなくなる。
len は後の操作のためにずっと持ち続ける情報なので、毎回引き継ぐ。

ステップ 4：composition を書く

composition(f, g) は g が先、f が後。 f(g(x)) を素直に展開する。

f(g(x)) = f.b·(g.b·x + g.c) + f.c = (f.b·g.b)·x + (f.b·g.c + f.c)

x の係数が新しい b、定数項が新しい c。

F composition(F f, F g) { return {f.b * g.b, f.b * g.c + f.c}; }
F id() { return {1, 0}; }

展開した結果がまた F の形に戻ることが大事。戻らない操作は遅延セグ木に乗らない。

確認：小さい例で手計算する

  • [1, 2, 3]（S = {6, 3}）に g: x → 2x + 1、そのあと f: x → 3x
  • 実際: [1, 2, 3] → [3, 5, 7] → [9, 15, 21]、和は 45
  • composition(f, g) = (3·2, 3·1 + 0) = (6, 3) → mapping: 6·6 + 3·3 = 45 ✓
  • 逆順 (6, 1) だと 6·6 + 1·3 = 39 でずれる（ダメ）