beet's soil

競プロのことなど

遅延評価セグメント木について

もう12月まじ?こわれる

【はじめに】

これの続きです。
beet-aizu.hatenablog.com

前提としてうし木(普通のセグメント木)までは理解しているものとします。

この記事では後述する  T=E の場合だけ取り上げましたがそうでない例が↓の後半にあります。
beet-aizu.hatenablog.com

【遅延評価セグメント木とは】

ある列に対して連続する区間に対して更新と取得ができるデータ構造である。以降遅延セグ木と略す。

前回のブログでは、要素の集合  T写像  f: T \times T \to T からなるモノイド  (T, f) を考えた。
遅延セグ木では、新たに作用素の集合  E写像  h: E \times E \to E からなるモノイド  (E, h) を追加し、
さらに作用としての写像  g: T \times E \to T を考える。
 f は要素と要素をマージする関数、  g は要素に作用素を作用させる関数、  h 作用素作用素をマージする関数である。


このとき、以下の性質を全て満たすなら、その要素と作用素の集合は遅延セグ木で扱うことができる。

  •  g( f(a,b) , c) = f(g(a,c), g(b,c)) \  (a,b \in T, c \in E)
  •  g (g(a,b),c) = g(a,h(b,c)) \ (a \in T, b,c \in E)
  •  e  E 単位元とすると、  g(a, e) = a \ (a \in T)
  •  f,g,h は十分高速に動作する )

上から順番に説明すると

  • 区間をマージしてから作用素を作用させても、作用素を作用させてから区間をマージするのと結果が同じ
  • 複数の作用素をマージして一度に作用させられること
  • 作用素を伝搬し終わっているのかの判定に必要(まあこれは満たされていなくても最悪どうにかなる)
  •  O(N) とかだと困る(setのマージとか)

具体例として以下のような問題を考える。

 N (1 \le N \le 10^5) 要素からなる数列  A が与えられる。 (1 \le A_i \le 10^9)
以下の二種類のクエリを  Q (1 \le Q \le 10^5) 個処理しなさい。
1.  A 区間  [l, r) の値の最大値を求める  (0 \le l \lt r \lt N)
2.  A 区間  [l, r) の値を  x に変更する  (0 \le l \lt r \lt N, 1 \le x \le 10^9)

クエリ1は整数の最大値であるから、 T は整数の集合  \mathbb{Z} に、 f max に対応する。
また、整数の最大値に関する単位元は (この問題では  1 \le A_i であるから)  0 である。

 g,h は代入演算である。また、この問題では 1 \le x \le 10^9 であるから  e = 0 \in E 単位元として

g(a,b) = \left\{\begin{array}{ll} 
a & (b = e) \\
b & (otherwise) 
\end{array} \right.
と定義すればよい。
 h についても同様に定義する。

上記の性質を満たしていることを確認する。

  •  g( f(a,b) , c) =  f(g(a,c), g(b,c))  である
  •  g (g(a,b),c) = g(a,h(b,c)) である
  • そのように定義した。
  •   f,g,h は全て  O(1) で動作する。

したがってこの問題は遅延セグ木によって解くことができる。


また、遅延セグ木は区間に対する操作が要素数に比例して変化する場合も解くことができる場合もある。
写像  p: E \times \mathbb{N} \to E を、 p(a,b) := g(\overbrace{a,a,\cdots, a}^{b個}) と定義する。
このとき  p が十分高速に動作するなら遅延セグ木で解くことができる。
また、条件も以下のようにすこし変化する。

  •  g( f(a,b) , p(c,d)) = f(g(a,p(c,d/2)), g(b,p(c,d/2))) \  (a,b \in T, c \in E, d \in \mathbb{N} )
  • 先程と同様
  • 先程と同様
  •  f,g,h,p は十分高速に動作する )

この場合の例も挙げておく。
RSQ and RAQ | Aizu Online Judge

Range Sum Query II

数列  A = {a_1, a_2, \cdots , a_n} に対し、次の2つの操作を行うプログラムを作成せよ。

add(s,t,x):  a_s, a_{s+1}, \cdots, a_t にxを加算する。
getSum(s,t):  a_s, a_{s+1}, \cdots, a_tの合計値を出力する。

ただし、 a_i (i=1, 2 , \cdots , n) は、0 で初期化されているものとする。

この問題では  T, E は共に整数(プログラム中ではint型)に、 f,g,h + に、 p \times に対応している。
また、 T, E f,hに関する単位元は共に  0 である。

条件を確認する。

  •  g( f(a,b) , p(c,d)) = a+b+(c \times d) = a+(c \times d/2)+b+(c \times d/2)  = f(g(a,p(c,d/2)), g(b,p(c,d/2)))  である
  •  g (g(a,b),c) = (a+b)+c = a + (b+c) = g(a,h(b,c)) である
  •  g(a,0) = a + 0 = a である
  •   f,g,h,p は全て  O(1) で動作する。

したがって、この問題も遅延セグ木で解くことができる。

実装例:
AIZU ONLINE JUDGE: Code Review


この問題においては g が可換であるため、後述するStarrySky木でも解くことができる。
実装例:
AIZU ONLINE JUDGE: Code Review



ここで、  p(a,b) := a と定義すれば区間に対しての操作の回数が比例しない場合にも対応できる。

以下にC++による実装例を載せておく。
(最新版はgithub参照のこと。)
library/chien.cpp at master · beet-aizu/library · GitHub

template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  typedef function<E(E,E)> H;
  typedef function<E(E,int)> P;
  int n;
  F f;
  G g;
  H h;
  P p;
  T d1;
  E d0;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(int n_,F f,G g,H h,T d1,E d0,
	      vector<T> v=vector<T>(),P p=[](E a,int b){return a;}):
    f(f),g(g),h(h),d1(d1),d0(d0),p(p){
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
    laz.clear();
    laz.resize(2*n-1,d0);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  inline void eval(int len,int k){
    if(laz[k]==d0) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1],laz[k]);
      laz[k*2+2]=h(laz[k*2+2],laz[k]);
    }
    dat[k]=g(dat[k],p(laz[k],len));
    laz[k]=d0;
  }
  T update(int a,int b,E x,int k,int l,int r){
    eval(r-l,k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k]=h(laz[k],x);
      return g(dat[k],p(laz[k],r-l));
    }
    return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
		    update(a,b,x,k*2+2,(l+r)/2,r));
  }
  T update(int a,int b,E x){
    return update(a,b,x,0,0,n);
  }
  T query(int a,int b,int k,int l,int r){
    eval(r-l,k);
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(int a,int b){
    return query(a,b,0,0,n);
  }
};

変数名は基本的に今までの説明と同じものを用いてある。
updateやqueryをする前にevalで遅延を伝搬している。
一回のクエリで遅延を伝搬する回数は高々  O(\log N) 回である。

【StarrySky木】

えー書こうと思っていたんですが遅延セグ木が使えるならあまり必要はないため省略します(ア)
すごく簡単に言うと操作が可換な場合に遅延評価をしないことで実装量が減って定数倍軽くなります。
一応githubのリンクだけ貼っておきます。
library/starrysky.cpp at master · beet-aizu/library · GitHub

【TODO】

遅延セグ木でも解ける。
RMQ 2 | Aizu Online Judge

図を作る。

【あとがき】

えー全体的に雑なのでわからないところがあったら教えてください(直すとは言ってない)
HL分解書くのに必要だったのでとりあえず書いたけどこれちゃんと書こうと思ったら一週間くらいかかりそう。