関数の合成

分配法則が成り立つならば、一次関数 \(x \mapsto ax+b\) は合成について閉じている。従って、結合法則が成り立つならば、半群になる。

• 分配束：min/max, gcd/lcm, bitwise-and/bitwise-or は分配則・結合則を満たすから、そのアフィン変換の合成は半群になる。どちらを +, × にしてもよい。
• max/plus を　+ / × に対応させると（熱帯）半環になる。
• bitwise-xor/bitwise-and を + / × に対応させると半環になる。

\(x\mapsto \left\lfloor \frac{ax+b}{c} \right\rfloor\) は合成について閉じており、半群になる。
積が最大となる部分区間（CF1692H）

// 区間 [L, R) の非空な部分区間の最大値を求める。
static class Interval {
    Interval leftMax;
    Interval rightMax;
    Interval max;
    int L;
    int R;
    long sum;
    
    public Interval(long sum, int L, int R) {
        this.L=L;
        this.R=R;
        this.sum=sum;
        leftMax=this;
        rightMax=this;
        max=this;
    }
    
    static Interval max(Interval a, Interval b) {
        if (a.sum > b.sum) return a;
        else return b;
    }
    
    static Interval merge(Interval a, Interval b) {
        if (a.R != b.L) throw new AssertionError();
        return new Interval(a.sum+b.sum, a.L, b.R);
    }
    
    static Interval op(Interval a, Interval b) {
        Interval ret=merge(a, b);
        ret.leftMax=Interval.max(a.leftMax, merge(a, b.leftMax));
        ret.rightMax=Interval.max(b.rightMax, merge(a.rightMax, b));
        Interval middleMax=merge(a.rightMax, b.leftMax);
        ret.max=Interval.max(Interval.max(a.max, b.max), middleMax);
        return ret;
    }
}

\(n\) 項間漸化式に従う数列 \(a\) が与えられる。
更新：\(L \leq i\leq R\) について、\(v_i \leftarrow v_i + Ca_{i-L}\)
出力：\(v_i\)

• 一般項が求まる場合：\(a_i\) の一般項は \(n\) 個の \(i^k\lambda^i\) の形の項の線形結合で表される。更新クエリは \(L \leq i \leq R\) について \((i-L)^k\lambda^{(i-L)}\) の形の項を足すと言い換えられて、変形するとやはり \(i^k\lambda^i\) の形の項の足し算になる。
• 一般項が求まらない場合：高速きたまさ法や行列累乗。

区間add, 区間和

長さ \(N\) の2つの数列 \(a, b\) が与えられる。
更新：\(a_L, a_{i+1}, \ldots, a_R\) に \(C\) を足す。
出力：\(\sum_{i=L}^R a_ib_i\)

と置く。\((p,q,r)=(a_R-a_{L-1}, \sum_{i=L}^{R} b_i, \sum_{i=L}^R a_i b_i)\)とすると\((p_1, q_1, r_1)*(p_2, q_2, r_2) = (p_1+p_2, q_1+q_2, r_1+r_2+p_1q_2)\)

Rolling Hash

ローリングハッシュは長さを持たせることで、モノイドになる。基底を \(b\) とする文字列 \(s\) のローリングハッシュを \(\beta(s)\) と置くと、\(s_1s_2\) のローリングハッシュは$$\beta(s_1)+\beta(s_2)b^{|s_1|+|s_2|}$$となる。従って、\((\beta(s), b^{|s|})\) がモノイドになる。文字列の更新などができる。