【アルゴリズム勉強】Segment Tree
いわゆるSeg木というもの真面目に勉強したのでその知見を残しておきます。
具体的には、以下のようなクエリに対数時間で答えることができます。
区間が与えられるので、その区間の最小値を出力してください。
区間の最小値は、
子の二つの区間の最小値の最小値になる
再帰的に子を見ていって、いい感じの区間になったら決めてく
uddate関数
code:cpp
void update(int i, int x){
//葉ノードの番号
i += N - 1;
//更新
//親へ登りながら更新
while(i > 0){
i = (i-1)/2;
//親ノードを更新する
}
}
query関数
code:cpp
ll query(int a, int b, int k, int l, int r){
//範囲外なら、INFを返す
if(r <= a || b <= l)return INF;
//範囲に入っているならそのnodeの数を返す
if(a <= l && r <= b)return valuek; else{
ll vl = query(a,b,k*2+1,l,(l+r)/2);
ll vr = query(a,b,k*2+2,(l+r)/2,r);
return min(vl,vr);
}
}
わかりにくかったところ
iの子が2 * i + 1, 2 * i + 2?
帰納的に示せるので使ってよし
iの親が(i-1)/2(小数切り捨て)
子の関係から明らか
木の葉の数Nはどうやって決めるの?
最終層、葉はn個以上はほしい
完全二分木なので、葉の数は2冪である必要がある
なので、n以上の最小の2冪をNとする
なぜNodeの数が全部で2 * N - 1個なの?
Nが二冪のとき、1 + 2 + 4 + 8 + ... + N/2はN-1になる(等比数列の和の関係から示せる)
ので、全部でNodeは N + N - 1で2 * N - 1
実装
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) typedef long long ll;
const ll INF = bit(31)-1;
int N;
vector<ll> value;
//i番目の葉:i + N - 1
//i番目のノードの子: 2 * i + 1, 2 * i + 2
//i番目のノードの親: (i - 1)/2
void update(int i, int x){
//葉ノードの番号
i += N - 1;
//更新
//親へ登りながら更新
while(i > 0){
i = (i-1)/2;
//子ノードを更新する
}
}
ll query(int a, int b, int k, int l, int r){
if(r <= a || b <= l)return INF;
if(a <= l && r <= b)return valuek; else{
ll vl = query(a,b,k*2+1,l,(l+r)/2);
ll vr = query(a,b,k*2+2,(l+r)/2,r);
return min(vl,vr);
}
}
int main() {
int n,q;
cin>>n>>q;
//葉の数Nをnを超える最小の2冪にする
N = 1;
while(n > N)N<<=1;
//初期化 Nodeの数は2 * N - 1、初期値はINF
value.assign(2 * N - 1,INF);
while(q--){
int c;
cin>>c;
if(c == 0){
int i,x;
cin>>i>>x;
update(i,x);
}
else{
int s,t;
cin>>s>>t;
cout<<query(s,t+1,0,0,N)<<endl;;
}
}
}
区間が与えられるので、その和を求めよ
区間の和は
子の区間の和の和だと考えることができるので
再帰的に子を見ていって、いい感じの区間になったら値を返すようにすればよい。
実装
0-indexedに注意
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) typedef long long ll;
const ll INF = bit(31)-1;
int N,q;
vector<ll> value;
//i番目の葉:i + N - 1
//i番目のノードの子: 2 * i + 1, 2 * i + 2
//i番目のノードの親: (i - 1)/2
void update(int i, int x){
//葉ノードの番号
i += N - 1;
//更新
//親へ登りながら更新
while(i > 0){
i = (i-1)/2;
//親ノードを更新する
}
}
ll query(int a, int b, int k, int l, int r){
if(r <= a || b <= l)return 0;
if(a <= l && r <= b)return valuek; else{
ll vl = query(a,b,k*2+1,l,(l+r)/2);
ll vr = query(a,b,k*2+2,(l+r)/2,r);
return vl+vr;
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int n;
cin>>n>>q;
N = 1;
while(n > N)N<<=1;
value.assign(2 * N - 1,0);
while(q--){
int com;
cin>>com;
if(com == 0){
ll i,x;
cin>>i>>x;
update(i-1,x);
//print(value);
}
else{
int s,t;
cin>>s>>t;
cout<<query(s-1,t,0,0,N)<<endl;;
}
}
}
参考