1. hotman78

    Posted

    hotman78
Changes in title
+【競プロ】セグ木は2冪で配列を取らなくていいという話と25行実装
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,36 @@
+#ごめんなさい
+可換性を必要とします
+#気持ち
+![DSC_0011.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68551/f49d0f38-14c9-f0f2-f281-0e2ba72c10d1.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(s,node[--r]);
+ l/=2;r/=2;
+ }
+ return s;
+ }
+ void update(auto t,T x){
+ t+=n;
+ while(t)f(node[t],x),t/=2;
+ }
+ T e=0;
+ void f(T& s,const T& t){
+ s+=t;
+ }
+};
+```
+
+#vertify
+[Range Sum Query(AOJ)](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B)