遅延セグ木

なんか分かった
多分ほとんどの人は知ってる

セグ木についての前提知識

セグ木については蟻本の実装で知ってるものとする
値を持つ配列の名前を sum 、モノイドの積を op(a,b) 単位元の名前を e とした時以下の様な実装
全体を覆うノードのインデックスを としている

int query(int a,int b,int k,int l,int r){//[l,r)を持つノードkに対して[a,b)のクエリ
  if(b<=l||r<=a)return e;//区間が交わってない
  if(a<=l&&b<=r)return sum[k];//ノードが完全に区間に含まれてる
  return op(query(a,b,k*2,l,(l+r)>>1),query(a,b,k*2+1,(l+r)>>1,r));
}

int query(int a,int b){
  return query(a,b,1,0,n);
}

遅延セグ木のお話

遅延セグ木で出来ることは以下（打つの面倒なので ACL 参照）

https://atcoder.github.io/ac-library/master/document_ja/lazysegtree.html

で、これを実現させるためにセグ木と違って各ノード はその区間の（モノイドとしての）和sum[k]だけでなく作用素func[k]も持たせるんだけど、ここがぼんやりとした理解だった

各ノード について、その祖先を に近い順に と並べた時、
写像の作用を全て行った後に作った仮想的な（通常の）セグ木でノードが持つ値をと置くと



が常に満たされるように情報を保持していることをしっかり念頭に置くと理解度が上がった

それを踏まえて実装で使う関数を書いていく
コードでもf∘gやf(v)の様な表記を使って見たけどこれは見辛かったかも

evaluation

inline void eval(int k){
  if(func[k]==id())return;
  sum[k]=func[k](sum[k]);
  if(k<n){
    func[k*2]=func[k]∘func[k*2];
    func[k*2+1]=func[k]∘func[k*2+1];
  }
  func[k]=id;
}

を（作用させてしまい）idにする関数
その後 に子がいるなら子に作用を渡す
先ほど書いた式が保持されることはすぐに分かる

update

inline void update(int a,int b,int k,int l,int r,F f){
  eval(k);
  if(a<=l&&r<=b){
    func[k]=f;
    eval(k);
  }
  else if(a<r&&l<b){
    //A
    update(a,b,k*2,l,(l+r)>>1,f);
    update(a,b,k*2+1,(l+r)>>1,r,f);
    sum[k]=op(sum[k*2],sum[k*2+1]);
  }
}

void update(int a,int b,F f){
  update(a,b,1,0,n,f);
}

区間 に作用素 を作用させる関数
見てるノードはセグ木のクエリと同じなのでイメージしやすいと思う（計算量も簡単）
基本的には を覆う様に取ってきたノードらに を与えるだけ

ここで重要なのが、各 で 最初に eval(k) を行っていることで、これにより常に今見てるノードの祖先の が であることが保証されている（従って が 祖先の との間に横入りしたりすることは無い）

しかし、それならばeval(k)を書くのは上記のコードのAの場所のみで十分ではと言う気持ちになる（その場合代入操作はfunc[k]=f∘func[k]になる）
コードで二箇所のeval(k)があるのはこれとは別の理由が存在するからで、 sum[k]=op(sum[k*2],sum[k*2+1]) で参照される際にfunc[k*2]やfunc[k*2+1]に作用が残っていると正しい値が上に伝わらないからである

query

inline S query(int a,int b,int k,int l,int r){
  eval(k);
  if(b<=l||r<=a)return e;
  if(l<=a&&b<=r)return sum[k];
  return op(query(a,b,k*2,l,(l+r)>>1,query(a,b,k*2+1,(l+r)>>1,r));
}

S query(int a,int b){
  return query(a,b,1,0,n);
}

updateと考え方はほぼ同じ
を見てる時は とその祖先の を全て処理し終わっているので sum[k] にその区間の値がきちんと入っている

全体のコード

template <class S,S (*op)(S, S),S (*e)(),
          class F,F (*composition)(F, F),F (*id)(),
                  S (*mapping)(F, S)>
//composition(f,g)はf(g())になる
struct LazySegmentTree{
  int n;
  vector<S> sum;
  vector<F> func;

  LazySegmentTree(int n_){
    n=1;
    while(n<n_)n<<=1;
    sum.resize(n*2,e());
    func.resize(n*2,id());
  }
  LazySegmentTree(vector<S>&v){
    n=1;
    while(n<v.size())n<<=1;
    sum.resize(n*2);
    func.resize(n*2,id());
    REP(i,v.size())sum[n+i]=v[i];
    for(int i=n-1;i;i--)sum[i]=op(sum[i*2],sum[i*2+1]);
  }

  inline void eval(int k){
    if(func[k]==id())return;
    sum[k]=mapping(func[k],sum[k]);
    if(k<n){
      func[k*2]=composition(func[k],func[k*2]);
      func[k*2+1]=composition(func[k],func[k*2+1]);
    }
    func[k]=id();
  }

  inline void update(int k,int l,int r,int a,int b,F f){
    eval(k);
    if(l<=a&&b<=r){
      func[k]=f;
      eval(k);
    }
    else if(l<b&&a<r){
      update(k*2+0,l,r,a,(a+b)>>1,f);
      update(k*2+1,l,r,(a+b)>>1,b,f);
      sum[k]=op(sum[k*2],sum[k*2+1]);
    }
  }

  void update(int l,int r,F f){
    update(1,l,r,0,n,f);
  }

  inline S query(int k,int l,int r,int a,int b){
    eval(k);
    if(l<=a&&b<=r)return sum[k];
    if(l<b&&a<r)return op(query(k*2,l,r,a,(a+b)>>1),query(k*2+1,l,r,(a+b)>>1,b));
    return e();
  }

  S query(int l,int r){
    return query(1,l,r,0,n);
  }
};

mappingやcompositionは ACL のドキュメント参照
func[k]==id()の部分が使いにくいかも？（構造体 に==を定義する必要があるので）