セグ木の初期化がボトルネックになる際の対処法3選
コード例は抽象化してません
あしからず
がちがちの動的セグ木を使う
コピペありの環境なら一番いいです
思想としてはポインタを使って必要になった時にノードを作るです
構築 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);}
};
急造動的セグ木を使う
クエリ
ICPC 等で、計算量に余裕がある場合もおすすめ
普段配列を使うところを map に置き換えるだけです
unordered_map にすれば
構築
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;
}
};
セグ木を使いまわす
使ったノードを初期値に戻す事で使いまわします
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();
}
};