セグ木の初期化がボトルネックになる際の対処法3選

コード例は抽象化してません
あしからず

1.がちがちの動的セグ木を使う

コピペありの環境なら一番いいです
思想としてはポインタを使って必要になった時にノードを作るです
構築O(1)です

template<typename T>
struct dynamic_segment{
    struct node;
    using np=node*;
    struct node{
        np ch[2]={0,0};
        T val=0;
    };
    np root=new node();
    np add(int64_t l,int64_t r,int64_t x,T val,np t){
        if(!(l<=x&&x<r))return t;
        if(!t)t=new node();
        t->val+=val;
        if(r-l==1)return t;
        int64_t m=(l+r)/2;
        t->ch[0]=add(l,m,x,val,t->ch[0]);
        t->ch[1]=add(m,r,x,val,t->ch[1]);
        return t;
    }
    T get(int64_t l,int64_t r,int64_t a,int64_t b,np t){
        if(!t)return 0;
        if(b<=l||r<=a)return 0;
        if(a<=l&&r<=b)return t->val;
        int64_t m=(l+r)/2;
        return get(l,m,a,b,t->ch[0])+get(m,r,a,b,t->ch[1]);
    }
    void add(int64_t x,T val){root=add(0,1LL<<32,x,val,root);}
    T get(int64_t l,int64_t r){return get(0,1LL<<32,l,r,root);}
};

2.急造動的セグ木を使う

クエリになりますが、ポインタに慣れてない人はこちらを使うのもいいかも
ICPC等で、計算量に余裕がある場合もおすすめ
普段配列を使うところをmapに置き換えるだけです
unordered_mapにすればになるのでちょっと速くなるかも知れないです
構築O(1)です

template<typename T>
struct dynamic_segment{
    map<int64_t,T>node;
    constexpr static int64_t sz=1LL<<32;
    void add(int64_t x,T val){
        x+=sz;
        while(x){
            node[x]+=val;
            x/=2;
        }
    }
    T get(int64_t l,int64_t r){
        l+=sz;r+=sz;
        T res=0;
        while(l<r){
			if(l&1)res+=node[l++];
			if(r&1)res+=node[--r];
			l/=2;r/=2;
		}
        return res;
    }
};

3.セグ木を使いまわす

10^5要素のセグ木を10^5回のループ毎に作らなければいけないみたいなパターンで使えます
使ったノードを初期値に戻す事で使いまわします

template<typename T>
struct dynamic_segment{
    vector<T>node;
    vector<int>used;
    int sz=1,n;
    dynamic_segment(int n):n(n){
        while(sz<n)sz*=2;
        node.resize(sz*2,0);
    }
    void add(int64_t x,T val){
        x+=sz;
        while(x){
            node[x]+=val;
            used.push_back(x);
            x/=2;
        }
    }
    T get(int64_t l,int64_t r){
        l+=sz;r+=sz;
        T res=0;
        while(l<r){
			if(l&1)res+=node[l++];
			if(r&1)res+=node[--r];
			l/=2;r/=2;
		}
        return res;
    }
    void clear(){
        for(auto e:used)node[e]=0;
        used.clear();
    }
};