sote2の競プロメモ

競プロを勉強する上で自分が覚えておきたいこと、かつ誰かの役にもたちそうなことを記事にします

セグメント木の配列について

たまにセグ木を配列として持っておきたいことがあります。
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];

のようにセグ木の配列を宣言しようとするとコンパイラに猛烈に怒られます。
f:id:sote2cpp:20200623022748p:plain
そこで、

   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を用いて初期化することもできました。
同じように困っている人の一助になれば幸いです。