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

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

可換性、不要...https://t.co/2yP0kCqrNP
— えびちゃん (@rsk0315_h4x) February 21, 2020

# 気持ち ![IMG_20200221_171036.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68551/8c54d358-0b6d-7f22-9b0e-92d00d3b4359.jpeg)

確かに上手く行きそう

実装

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

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};
	}
};

verify

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