遅延伝播セグメント木について（旧：遅延評価セグメント木について）

もう12月まじ？こわれる

はじめに

先にこっちを見て　
beet-aizu.hatenablog.com

2019/05/06 編集　
遅延評価を遅延伝播に変更
問題例へのリンク↓を追加
beet-aizu.hatenablog.com

【はじめに】

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

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

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

【遅延伝播セグメント木とは】

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

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

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

• g(f(a,b),c)=f(g(a,c),g(b,c)) (a,b∈T,c∈E)$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∈T,b,c∈E)$g(g(a,b),c)=g(a,h(b,c))(a\in T,b,c\in E)$
• e$e$ を E$E$ の単位元とすると、 g(a,e)=a (a∈T)$g(a,e)=a(a\in T)$
• （ f,g,h$f,g,h$ は十分高速に動作する ）

上から順番に説明すると

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

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

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

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

g,h$g,h$ は代入演算である。また、この問題では1≤x≤109$1\le x\le {10}^9$ であるから e=0∈E$e=0\in E$ を単位元として
g(a,b)={ab(b=e)(otherwise)$g(a,b)=\{\begin{array}{ll}a& (b=e)\\ b& (otherwise)\end{array}$
と定義すればよい。
h$h$ についても同様に定義する。

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

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

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

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

• g(f(a,b),p(c,d))=f(g(a,p(c,d/2)),g(b,p(c,d/2))) (a,b∈T,c∈E,d∈N)$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$f,g,h,p$ は十分高速に動作する ）

この場合の例も挙げておく。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G&lang=jp

Range Sum Query II

数列 A=a1,a2,⋯,an$A=a_1,a_2,\cdots ,a_n$に対し、次の２つの操作を行うプログラムを作成せよ。

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

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

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

条件を確認する。

• g(f(a,b),p(c,d))=a+b+(c×d)=a+(c×d/2)+b+(c×d/2)=f(g(a,p(c,d/2)),g(b,p(c,d/2)))$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(g(a,b),c)=(a+b)+c=a+(b+c)=g(a,h(b,c))$ である
• g(a,0)=a+0=a$g(a,0)=a+0=a$ である
• f,g,h,p$f,g,h,p$ は全て O(1)$O(1)$ で動作する。

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

実装例:
AIZU ONLINE JUDGE: Code Review

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

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

以下にC++による実装例を載せておく。
（最新版はgithub参照のこと。）
https://github.com/beet-aizu/library/blob/master/segtree/chien.cpp

2019/12/17追記
ディレクトリ構造を変えるとURLも変わるのを忘れていました
新しいURLです　あとpに対応するものが消えました　
beet-aizu.github.io

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(logN)$O(\log N)$ 回である。

【StarrySky木】

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

2019/12/17追記　StarrySkyは使わないので消しました　全部遅延でOK

【TODO】

遅延セグ木でも解ける。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3024

図を作る。

【あとがき】

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