セグメント木の配列について
たまにセグ木を配列として持っておきたいことがあります。
atcoder.jp
この問題の想定解はsetの二分探索ですが、
セグ木の配列があればぶん殴ることができます。
僕のライブラリのセグ木はもともと
struct SegmentTree { private: int n; vector<int> node; public: SegmentTree(vector<int> v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, 0); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } void update(int x, int val) { // 最下段のノードにアクセスする x += (n - 1); // 最下段のノードを更新したら、あとは親に上って更新していく node[x] = val; while(x > 0) { x = (x - 1) / 2; node[x] = min(node[2*x+1], node[2*x+2]); } } int getsum(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = getsum(a, b, 2*k+1, l, (l+r)/2); int vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } };
のような感じで、デフォルトコンストラクタ(引数なしで宣言した時に自動でそれにより初期化する)がありませんでした。
この状態で
SegmentTree seg[10];
のようにセグ木の配列を宣言しようとするとコンパイラに猛烈に怒られます。
そこで、
SegmentTree() { vector<int> v(0); int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, 0); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2]; }
というようにデフォルトコンストラクタをstructに追加してあげました。
すると、コンパイルが通り、後からセグ木配列の要素を別のvector
同じように困っている人の一助になれば幸いです。