1. hotman78

    No comment

    hotman78
Changes in body
Source | HTML | Preview
@@ -1 +1,47 @@
-現在補修中
+#えびちゃんありがとうの章
+~~可換性を必要とします~~
+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,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)](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B)
+[タコヤキオイシクナール(atcoder)](https://atcoder.jp/contests/arc008/tasks/arc008_4)