これを参考に．
できる（と思っている）こと
集合 \(A\) について順序関係 \(\le\) が定義されているとします *1 ． また，\(A\) の元について演算 \(\oplus\) が定義されていて，\(\oplus\) には逆演算 \(\ominus\) も定義されているとします．
追記
ほんとはちゃんと仮定を書かなきゃなんですが，甘えます．
「集合 A について順序関係 ≤ が定義されているとします.」の周辺は (厳密さを装おっている以上は) もう少し正確に書くべきだと思います。 (演算が結合性と可換性を持ちかつ順序を保存することが無言で仮定されてしまっています)
— うさぎ (@a3VtYQo) June 21, 2019
追記おわり
集合 \(A\) の要素からなる 0-indexed な配列 \(a[N]\) に対して以下の処理を \(O(\log N)\) 時間で行います．
- \(0 \le L \le i \le R < N\), \(x \in A\) に対して \(a_i\) を \(a_i \oplus x\) で更新する．
- \(\mathrm{\max}_{0 \le L \le i \le R < N}\, a_i\) を求める．
当然なんですが，遅延伝搬セグメント木でも同様の処理を行うことができます．
アイディア
まず，\(N\) を 2 べきになるように調整して，これを \(N\) と置き直します． 1-indexed な配列 \(B[2N-1]\) を用意して，二分木として扱います．\(b_i\) の子が \(b_{2i}\) と \(b_{2i+1}\) で，\(b_1\) が根です．
根ノード \(b_1\) は全体の最大値を実際に持つようにします．
\(b_{i+N}\) は \(a_i\) の値を持ち， それ以外のノード \(b_i\) は部分木の最大値を持つんですが，これらはその値を実際に持つわけではなく，差分を持ちます．
例を見た方がつかみやすい気がするので，例を書きます（甘え）． まず，\(A\) が以下のようだとします．
3 1 4 1 5 9 2 6
いわゆる普通のセグメント木で管理した場合の二分木は以下のようになるはずです．
9
4 9
3 4 9 6
3 1 4 1 5 9 2 6
このとき，\(B\) の表す二分木は以下のようになります．
9
-5 0
-1 0 0 -3
0 -2 0 -3 -4 0 -4 0
親と等しい，すなわち兄弟より小さくないノードについては \(0\) にし，そうでないノードについては自分の値から兄弟の値を引いたものを持たせます．ある兄弟について，\(0\) でない値を持つノードは高々ひとつになるように管理します．
根から葉まで加算しながら辿ると元の値を復元できます．
区間に対して更新することを考えます．
\(a_0\) から \(a_6\) に \(2\) を足すのを例に考えます．
以下で [] で括ったノードに \(2\) を足します．
9
[-5] 0
-1 0 [0] -3
0 -2 0 -3 -4 0 [-4] 0
これらのノードは，非再帰セグ木の気持ちになると簡単に得られます． で，実際に足すと次のようになります．
9
-3 0
-1 0 2 -3
0 -2 0 -3 -4 0 -2 0
あるノードに加算したとき，その部分木を更新する必要はないのがうまいポイントです．
なんですが，このとき兄弟の両方が \(0\) でない値を持つノードが存在しえます．右下の 2 と -3 のところが該当します．
なので，これを根方向に辿りながら修正します．
まずこうなって，
9
-3 2
-1 0 0 -5
0 -2 0 -3 -4 0 -2 0
こう．
11
-5 0
-1 0 0 -5
0 -2 0 -3 -4 0 -2 0
親が \(a\) で子が \( (b, c)\) (\(b \le c\)) のとき，\(a \gets a\oplus c\), \(b \gets b\ominus c\), \(c\gets 0\) と更新します．
えー，つかれちゃった．
全体の最大値は根を見るだけでよくて，任意区間の最大値は普通のセグ木でやるようにがんばるといいです．
提出コード を参考にしてください． これは非再帰セグ木がわかっている前提ぽい．Starry-sky 木自体は再帰でも実装できます．
非再帰セグ木を知らない人は これ とか これ を見るといいと思います．
おわり
若干投げやりになっちゃってごめんなさいなんですが，これは主に以下のような理由です．
まず，遅延セグ木より扱える対象が少ないのがあって，もっとちゃんと考察するといろいろできる気もするんですが，なんにせよ逆元は必要になるはずなので．
それから，根だけ実際の値を持つ関係で，大きさが二べきでないとつらくて，これも考えてやるとどうにかなるかもなんですが，そうするくらいなら遅延セグ木でよくないかとなってしまうため．
遅延セグ木はかっこいい．非再帰はさらにかっこいい．
にゃんこ．
