[1] 遅延セグメント木とは

遅延セグメント木は，通常のセグメント木を拡張し，区間に対する更新操作も高速に処理できるようにしたデータ構造です．

今回の問題では，次の \(2\) 種類のクエリをそれぞれ \(O(\log N)\) 時間で処理します．

• 区間加算：指定された区間のすべての要素に整数 \(x\) を加える．
• 区間最小値取得：指定された区間の最小値を求める．

---

[2] 遅延セグメント木の実装

今回は，通常のセグメント木の再帰的な実装を拡張する形で，遅延セグメント木を実装します．

[2.1] 不変条件と遅延情報

通常のセグメント木では，各ノードに担当区間の最小値を保持しました．

遅延セグメント木では，区間加算を子孫のノードにすぐには反映せず，遅延情報として保持することを考えます．

具体的には，各ノード \(i\) に対して，次の \(2\) つの値を保持します．

• dat[i]：区間最小値を管理するための値．
• lazy[i]：子孫のノードにはまだ反映していない加算量．

これらについて，次の不変条件を維持します．

• ノード \(i\) の担当区間の最小値は，dat[i] に，ノード \(i\) のすべての真の祖先 \(j\) の lazy[j] を加えた値に等しい．

つまり，ノード \(i\) の担当区間を \(I_i\) とすると，

\[ \min_{k\in I_i} A[k] = \mathrm{dat}[i] + \sum_{\substack{j:\,\text{$j$ は $i$ の真の祖先}}} \mathrm{lazy}[j] \]

が成立するようにします．この不変条件を保ちながら，区間加算と区間最小値取得を効率よく処理する方法を考えます．

[2.2] 遅延情報の伝搬

ノード \(i\) に lazy[i] = x が保持されている場合，左右の子について dat と lazy に \(x\) を加算し，最後に lazy[i] を \(0\) に戻します．

void push(int i) {
  ll x = lazy[i];
  dat[2 * i] += x;
  lazy[2 * i] += x;
  dat[2 * i + 1] += x;
  lazy[2 * i + 1] += x;
  lazy[i] = 0;
}

この操作によって，ノード \(i\) の担当区間の最小値を変えることなく，遅延情報を子へ移動させることができます．また，この操作の前後で [2.1] の不変条件は維持されます．

[2.3] 区間加算

区間加算も，通常のセグメント木の再帰的な区間クエリと同じように，ノードの担当区間と更新区間の関係で場合分けします．

ノード \(i\) の担当区間を \([\mathrm{node\_L},\mathrm{node\_R})\)，加算する区間を \([L,R)\) とします．

再帰関数 apply_rec は，次の仕様を満たすように実装します．

事前条件

• ノード \(i\) を根とする部分木内で，[2.1] で説明した不変条件が成立している．
• ノード \(i\) のすべての真の祖先 \(j\) について，lazy[j] = 0 である．

終了時に保証すること

• 区間 \([\mathrm{node\_L},\mathrm{node\_R})\) と \([L,R)\) の共通部分に含まれる列 \(A\) の要素に \(x\) が加算され，それ以外の要素の値は変更されない．
• ノード \(i\) を根とする部分木内で，不変条件が引き続き成立している．
• ノード \(i\) の真の祖先の lazy は \(0\) のままである．

この仕様を満たすために，次の \(3\) 通りに場合分けします．

1. 共通部分がない場合：何もせず終了する．
2. ノードの担当区間がすべて含まれる場合：dat[i] と lazy[i] に \(x\) を加えて終了する．
3. それ以外の場合：push(i) してから左右の子を再帰的に更新し，最後に dat[i] を再計算する．

実装は次のようになります．

// [node_L, node_R) と [L, R) の共通部分に x を加算する
// 事前条件：ノード i の真の祖先の lazy はすべて 0
// 終了時：区間加算が反映され，ノード i の部分木内で不変条件が維持される
void apply_rec(int i, int node_L, int node_R,
               int L, int R, ll x) {
  // 共通部分がない
  if (node_R <= L || R <= node_L) return;

  // ノードの区間全体が含まれる
  if (L <= node_L && node_R <= R) {
    dat[i] += x;
    lazy[i] += x;
    return;
  }

  // 左右の子を再帰的に処理する
  push(i);
  int m = (node_L + node_R) / 2;
  apply_rec(2 * i, node_L, m, L, R, x);
  apply_rec(2 * i + 1, m, node_R, L, R, x);
  dat[i] = min(dat[2 * i], dat[2 * i + 1]);
}

void apply(int L, int R, ll x) {
  apply_rec(1, 0, seg_size, L, R, x);
}

この実装が仕様を満たすことは，再帰的に確認できます．

共通部分がない場合は何も変更しません．ノードの担当区間がすべて含まれる場合は，dat[i] と lazy[i] に \(x\) を加えることで，その区間への加算を表現できます．

それ以外の場合には，push(i) によって lazy[i] = 0 としてから左右の子を再帰的に処理します．これにより，左右の子についても apply_rec の事前条件が成立します．

再帰呼び出しの終了後には，lazy[i] = 0 であり，左右の子の情報も更新されているため，

dat[i] = min(dat[2 * i], dat[2 * i + 1]);

によってノード \(i\) の情報を再計算できます．根からの呼び出しが終了した時点では，木全体で不変条件が成立します．

ノードの担当区間が更新区間に完全に含まれる場合には，子孫に進まずに処理を終了します．したがって，通常のセグメント木の区間クエリと同様に，計算量は \(O(\log N)\) です．

push を省略する実装について

今回の区間加算のように作用が可換な場合には，`push` を行わずに区間加算を実装する方法もあります． ただし，一般の作用では適用順序が重要になるため，同じ方法が使えるとは限りません．そのため，本解説では `push` を行う実装を採用しています．

[2.4] 区間最小値取得

区間最小値取得も，通常のセグメント木の再帰型の実装とほとんど同じです．

prod_rec についても，呼び出し時点でノード \(i\) のすべての真の祖先の lazy が \(0\) であることを仮定します．この条件により，ノードの担当区間が求めたい区間に完全に含まれる場合には，dat[i] をそのまま返すことができます．

それ以外の場合には，左右の子を再帰的に調べる前に push(i) を行います．これにより，左右の子についても同じ事前条件が成立します．

// ノード i は区間 [node_L, node_R) を担当する
// 返り値は [node_L, node_R) と [L, R) の共通部分の最小値
// 事前条件：ノード i の真の祖先の lazy はすべて 0
ll prod_rec(int i, int node_L, int node_R, int L, int R) {
  if (node_R <= L || R <= node_L) return INF;
  if (L <= node_L && node_R <= R) return dat[i];

  push(i);
  int m = (node_L + node_R) / 2;
  ll x = prod_rec(2 * i, node_L, m, L, R);
  ll y = prod_rec(2 * i + 1, m, node_R, L, R);
  return min(x, y);
}

ll prod(int L, int R) {
  return prod_rec(1, 0, seg_size, L, R);
}

prod の中でも push が呼ばれるため，データ構造内部の情報は変更されますが，列 \(A\) の各要素の値は変化しません．

計算量は \(O(\log N)\) です．

[2.5] 解答例

遅延セグメント木の初期構築は，セグメント木の初期構築と同じように行えます．これまでの内容を踏まえた解答例は次の通りです．

• 解答例：https://atcoder.jp/contests/aalc001/submissions/79976703

[2.6] 非再帰的な実装について

遅延セグメント木も，通常のセグメント木と同様に，再帰関数を用いずに実装できます．

通常のセグメント木では，区間 \([L,R)\) を \(O(\log N)\) 個のノードが担当する区間に分割して，区間最小値を計算しました．遅延セグメント木では，この分割に対応するノードに加えて，それらの祖先のノードを処理することを考えます．

これまで説明した再帰的な実装の処理は，次のように整理できます．

• 区間加算：祖先から順に遅延情報を push し，区間分割に対応するノードに加算を行い，最後に祖先の情報を下から順に再計算する．
• 区間最小値取得：祖先から順に遅延情報を push し，区間分割に対応するノードの値の最小値を求める．

区間をノードに分割する方法は，通常のセグメント木の非再帰的な実装と同じです．あとは，必要な祖先のノードを列挙できればよく，これも単純なインデックス計算によって実現できます．

このようにして，区間加算・区間最小値取得をそれぞれ \(O(\log N)\) 時間で処理できます．

具体的な実装については，AtCoder Library のソースコードを参照してください．

• 「lazysegtree.hpp」（AtCoder Library）

---

[3] AtCoder Library を使う場合

AtCoder Library には，遅延セグメント木の実装 atcoder::lazy_segtree が用意されています．

• 「Lazy Segtree」（AtCoder Library）

利用する際には，通常のセグメント木で指定した情報に加え，区間に作用させる操作と，それを合成する方法を指定します．

今回の場合，次のように設定できます．

• S = ll：区間の最小値．
• op(a,b) = min(a,b)：区間情報の結合．
• e() = INF：区間最小値の単位元．
• F = ll：区間に加算する値．
• mapping(f,x) = x+f：最小値に加算を反映する操作．ただし，単位元 INF は INF のままとする．
• composition(f,g) = f+g：複数の加算の合成．
• id() = 0：何も加算しない操作．

using ll = long long;
using S = ll;
using F = ll;

S op(S a, S b) {
  return min(a, b);
}

S e() {
  return INF;
}

S mapping(F f, S x) {
  return (x == INF ? INF : x + f);
}

F composition(F f, F g) {
  return f + g;
}

F id() {
  return 0;
}

これらを指定することで，初期列 A から遅延セグメント木を構築できます．

atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);

構築後は，次の操作を使用します．

• seg.apply(L,R,x)：半開区間 \([L,R)\) のすべての要素に \(x\) を加える．
• seg.prod(L,R)：半開区間 \([L,R)\) の最小値を求める．

いずれも \(O(\log N)\) 時間で処理できます．

• 解答例（ACL）：https://atcoder.jp/contests/aalc001/submissions/79976714