1. hotman78

    No comment

    hotman78
Changes in body
Source | HTML | Preview
@@ -1,40 +1,41 @@
#謝らないよ
~~可換性を必要とします~~
f(s,node[--r]);をf(node[--r],s);に変えると可換性を要求せずにすむらしいです(凄い)
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">可換性、不要...<a href="https://t.co/2yP0kCqrNP">https://t.co/2yP0kCqrNP</a></p>&mdash; えびちゃん (@rsk0315_h4x) <a href="https://twitter.com/rsk0315_h4x/status/1230769796662194178?ref_src=twsrc%5Etfw">February 21, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
#気持ち
![IMG_20200221_171036.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68551/8c54d358-0b6d-7f22-9b0e-92d00d3b4359.jpeg)
確かに上手く行きそう
#実装
非再帰です
```c++:segment.cpp
template<typename T>
struct segment{
vector<T> node;
int n;
segment(int n):n(n){node.assign(n*2+1,e);}
T get(auto l,auto r){
l+=n;r+=n;
T s=e;
while(l<r){
- if(l&1)f(s,node[l++]);
- if(r&1)f(node[--r],s);
+ if(l&1)s=f(s,node[l++]);
+ if(r&1)s=f(node[--r],s);
l/=2;r/=2;
}
return s;
}
void update(auto t,T x){
t+=n;
- while(t)f(node[t],x),t/=2;
+ node[t]=f(node[t],x);
+ while(t>1)t/=2,node[t]=f(node[t*2],node[t*2+1]);
}
T e=0;
- void f(T& s,const T& t){
- s+=t;
+ T f(const T& s,const T& t){
+ return s+t;
}
};
```
#vertify
[Range Sum Query(AOJ)](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B)