メモ

この記事では遅延セグメント木の「気持ち」を説明します。
通常のセグメント木に関する知識を前提とします。
アルゴリズムの説明のみであり、実装については一切説明していません。
基本的には以下のサイトの記述を、自分好みにリライトしたものです。
beet-aizu.hatenablog.com

○遅延セグメント木とは

半群 $(M,\cdot)$
作用素モノイド $\DeclareMathOperator{\id}{id}(\{T:M\to M\},\circ,\id)$ の部分モノイド $E$
$E\to E$ の写像 $f$
があり、次の(1)～(3)の条件を満たすとする。
(1) $M$ の演算、作用素の適用、作用素の合成はいずれも $O(1)$ で行える
(2) $f^k(T)$ は $T$ にも $k$ にも依らず $O(1)$ で計算できる
(3) $\forall T\in E.\ \forall x,y \in M.\ (Tx)(Ty)=f(T)(xy)$ *1

このとき $M$ 上の長さ $N$ の列 $\{a_i\}$ に対する2種類のクエリ(i)(ii)を遅延セグメント木によって $O(\log N)$ で処理することができる
(i)区間更新クエリ：区間 $I$ と作用素 $T\in E$ が与えられ、全ての $i\in I$ について $a_i$ を $Ta_i$ に更新する
(ii)区間計算クエリ：区間 $I=[l,r)$ が与えられ、 $a_l a_{l-1} \ldots a_{r-1}$ を求める

○実現する方法
通常のセグメント木では区間の積の情報を持っていたが、遅延セグメント木ではそれに加え、その区間全体に作用する作用素の情報を持つ。
これだけ。

○ $O(\log N)$ でクエリが処理できることの確認
各nodeが長さを $2^k$ の区間 $I$ の情報を $(x,T)$ の形で持っているとする。
・区間更新クエリ
区間 $J$ と作用素 $S$ が与えられたとする。上から順に次のように各nodeを更新する。
(1) $I \subset J$ のとき
$(x,T)$ を $(x,ST)$ に更新する
(2) $I \cap J=\emptyset$ のとき
何もしない
(3)それ以外のとき
次の3つのことを行う
１． $T$ を子nodeに伝播する。即ち、子nodeが $(x',T')$ であるとき、これを $(x',TT')$ に更新する
（↑これが肝となる遅延伝播）
２．子nodeを再帰的に更新する
３．子nodeの更新結果を元に自身のnodeが持つべき値 $y$ を計算し、 $\DeclareMathOperator{\id}{id}(y,\id)$ に更新する
以上の操作は $O(\log N)$ 個のnodeを $O(1)$ で更新するので $O(\log N)$ となる。
・区間計算クエリ
区間 $J$ が与えられたとする。上から順に次のように、各nodeを更新しながら値を計算する
(1) $I \subset J$ のとき
$f^k(T)(x)$ を返す
(2)それ以外のとき
次の3つのことを行う
１． $T$ を子nodeに伝播する。即ち、子nodeが $(x',T')$ であるとき、これを $(x',TT')$ に更新する
２．自身のnodeを、 $\DeclareMathOperator{\id}{id}(f^k(T)(x),\id)$ に更新する
（更新クエリと違って値が変化しないので子を見る必要がない）
３．子nodeを再帰的に呼び出して値を計算したものを返す
以上の操作は $O(\log N)$ 個のnodeを $O(1)$ で更新/計算するので $O(\log N)$ となる。

○自明な例
・区間加算クエリ＋区間和クエリ
$M=(M,+),\\ E=\{x \mapsto x+k\ |\ k\in M\},\\ f(T)=T^2$
・区間加算クエリ＋区間maxクエリ
$M=(M,\max),\\ E=\{x \mapsto x+k\ |\ k\in M\},\\ f(T)=T$
・区間変更クエリ＋区間和クエリ
$M=(M,+),\\ E=\{x \mapsto k\ |\ k\in M\}\cup\{\DeclareMathOperator{\id}{id}\id\},\\ f(x \mapsto k)=(x \mapsto 2k)$
・区間変更クエリ＋区間maxクエリ
$M=(M,\max),\\ E=\{x \mapsto k\ |\ k\in M\}\cup\{\DeclareMathOperator{\id}{id}\id\},\\ f(T)=T$

○非自明な例１
$\mathbb{Z}$ の数列 $\{a_i\}$ が与えられる。次のクエリに答えよ
(i)区間加算クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $a_i+k$ に更新する
(ii)区間変更クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $k$ に更新する
(iii)区間計算クエリ：区間 $I=[l,r)$ が与えられ、 $a_l+a_{l-1}+\ldots+a_{r-1}$ を求める

$M=(\mathbb{Z},+),\\ E=\{x \mapsto x+k\ |\ k\in \mathbb{Z}\}\cup\{x \mapsto k\ |\ k\in \mathbb{Z}\},\\ f(x \mapsto x+k)=(x \mapsto x+2k),\\ f(x\mapsto k)=(x\mapsto 2k)$
（ $E$ が写像の合成で閉じていることを確かめよ）

○非自明な例２
$\mathbb{Z}$ の数列 $\{a_i\}$ と $\{b_i\}$ が与えられる。次のクエリに答えよ
(i)区間更新クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $a_i+b_i k$ に更新する
(ii)区間計算クエリ：区間 $I=[l,r)$ が与えられ、 $a_l+a_{l-1}+\ldots+a_{r-1}$ を求める

$M=(\mathbb{Z}^2,+),\\ E=\{(a,b) \mapsto (a+bk,b)\ |\ k\in \mathbb{Z}\},\\ f(T)=T$

○非自明な例３
$X=\{0,1,2,3,\infty\}$ とする。 $X$ 上の演算 $+$ を
$a+b=\begin{cases} a+b & \text{($\mathbb{Z}\cup \{\infty\}$の元として) $a+b\leq 3$のとき}\\ \infty & \text{($\mathbb{Z}\cup \{\infty\}$の元として) $a+b\geq 4$のとき} \end{cases}$
により定める。
$X$ の数列 $\{a_i\}$ が与えられる。次のクエリに答えよ
(i)区間更新クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $a_i+k$ に更新する
(iii)区間計算クエリ：区間 $I$ と値 $n$ が与えられ、 $\#\{i\in I\ |\ a_i=n\}$ を求める

$M=(\mathbb{Z}^5,+),\\ \begin{array}{rl} E=\{&(x_0,\ldots,x_4)\mapsto(x_0,x_1,x_2,x_3,x_4),\\ &(x_0,\ldots,x_4)\mapsto(0,x_0,x_1,x_2,x_3+x_4),\\ &(x_0,\ldots,x_4)\mapsto(0,0,x_0,x_1,x_2+x_3+x_4),\\ &(x_0,\ldots,x_4)\mapsto(0,0,0,x_0,x_1+x_2+x_3+x_4),\\ &(x_0,\ldots,x_4)\mapsto(0,0,0,0,x_0+x_1+x_2+x_3+x_4)\}, \end{array} \\ f(T)=T$

○余談1
仮定(2)を「 $f(T)$ は $T$ に依らず $O(1)$ で計算できる」と弱めるとクエリ当たり $O( (\log N)^2)$ となる。
ただし、そのかわりに次の条件を仮定すると $O(\log N)$ で計算可能である。
(2)' $f$ が単射かつ $f(T),f^{-1}(T)$ は $T$ に依らず $O(1)$ で計算できる
この場合、各nodeは $(x,f^k(T))$ の形で情報を持てばよい。
例えば上で挙げた7つの例は全て(2),(2)'の仮定をともに満たす。
(2)と(2)'の仮定をともに満たす場合、各nodeの情報を $(x,T)$ の形で持つ流儀の人と、 $(x,f^k(T))$ の形で持つ流儀の人がいるため、他人の説明/コードを読む際は、どちらの流儀で書かれたものが注意する必要がある。

○余談1の余談
(2)と(2)'は独立な条件か？
・「(2)を満たし(2)'を満たさないもの」の例としては、区間乗算＋区間総積クエリなどがある。
$f(x\mapsto kx)=(x\mapsto k^2 x)$ なので、 $k=-1$ のときを考えるとこれは単射ではない。
しかしこれは $E'=\{(n,k)\ |\ n,k\in \mathbb{Z}_{\geq 0}\}$ で考えることで単射とみなすことができる。
（ $E'$ の $\mathbb{Z}$ への作用は $(n,k)(x)=(-1)^n k x$ とする）
本質的にダメな例があったら教えて
・「(2)'を満たし(2)を満たさないもの」の例は思いついてないので誰か教えて

○余談2
上で挙げた例は、全て $M$ を適切に取り直すことで、 $f(T)=T$ とすることができる。
そうすることが出来ない例があったら教えて

*1: よく考えると課すべき条件はT(xy)=(f(T)x)(f(T)y)だったが、ここを変更すると記事全てを書き直す必要があること、現在の条件でも整合性はあること、の2点を理由に修正は行わない

問題はこちら
No.657 テトラナッチ数列 Easy - yukicoder

T0=1として、n=0から数列が始まるとしてよい。
フィボナッチ数列同様、直前の4項を持って漸化式で求めることができる。
直前の4項は17^4=83521状態なので、高々83521の周期を持つ。
具体的に計算することで4912の周期をもつことがわかるので逐次計算すれば良い。

int main(){
	int q;
	scanf("%d",&q);
	while(q--){
		long n;
		scanf("%ld",&n);
		n%=4912;
		int a=1,b=0,c=0,d=0;
		while(n--){
			int t=(a+b+c+d)%17;
			a=b;
			b=c;
			c=d;
			d=t;
		}
		printf("%d\n",a);
	}
}

この手のものはループでやるか再帰でやるか悩むが、代入が多いので再帰でやったほうがよさそう。
出力まで再帰関数のなかでやってしまうことにするといろいろ噛み合う。
main再帰より通常の再帰の方が1B短い

i,n;
main(a,b,c,d){n--%4912<1?++i>2&&printf("%d\n",d),~scanf("%d",&n)&&main(0,0,0,1):main((a+b+c+d)%17,a,b,c);}

n;
f(a,b,c,d){n--%4912?f(b,c,d,(a+b+c+d)%17):printf("%d\n",a);}
main(i){for(;~scanf("%d",&n);--i&&f(1,0,0,0));}

これで完成……といいたいところだが、%17をつける位置を第4引数から第3引数に変更することでカッコを外せる。
これにより第4引数は再帰のたびに大きくなることになるが、a+b+c<51なので1回の再帰で高々51しか増加せず、再帰回数は4912回以下なのでオーバーフローの心配はない

n;
f(a,b,c,d){n--%4912?f(b,c,d,(a+b+c+d)%17):printf("%d\n",a);}
main(i){for(;~scanf("%d",&n);--i&&f(1,0,0,0));}

107B

メモ

yukicoderでゆるふわgolf

yukicoder No.671 1000000007

遅延セグメント木

yukicoder No.658 テトラナッチ数列 Hard

yukicoder No.657 テトラナッチ数列 Easy

yukicoder No.656 ゴルフ