1. hotman78

    No comment

    hotman78
Changes in body
Source | HTML | Preview

えびちゃんありがとうの章

可換性を必要とします
f(s,node[--r]);をf(node[--r],s);に変えると可換性を要求せずにすむらしいです(凄い)

気持ち

IMG_20200221_171036.jpg

確かに上手く行きそう

実装

非再帰です/可換性を要求しません

segment.cpp
template<typename T>
struct segment{
    vector<T> node;
    int n;
    segment(int n):n(n){node.assign(n*2,e);}
    T get(int l,int r){
        l+=n;r+=n;
        T s=e,t=e;
        while(l<r){
            if(l&1)s=f(s,node[l++]);
            if(r&1)t=f(node[--r],t);
            l/=2;r/=2;
        }
        return f(s,t);
    }
    void update(int t,T x){
        t+=n;
        node[t]=f(node[t],x);
        while(t>1)t/=2,node[t]=f(node[t*2],node[t*2+1]);
    }
    void change(int t,T x){
        t+=n;
        node[t]=x;
        while(t>1)t/=2,node[t]=f(node[t*2],node[t*2+1]);
    }
    T e={1,0};
    T f(const T& s,const T& t){
        return {t.first*s.first,t.first*s.second+t.second};
    }
};

vertify

Range Sum Query(AOJ)
タコヤキオイシクナール(atcoder)