세그먼트 트리
구간 질의를 진행할때 Segment Tree를 자주 사용한다.
Segment Tree를 기본적으로는 Top-Down 방식을 사용한다.
https://m.blog.naver.com/kks227/220791986409 참조
이 포스트에서는 Segment Tree를 Bottom - up 방식으로 구현할 것이다.
먼저 segment Tree를 bottom up 방식으로 구현하기 위해서는 PerfectBinary tree로 만들어야 한다. 즉 배열의 개수가 $ n = 2^k$ 이어야 한다는 점이다.
이때 n이 $2^k$가 아닌 수인 경우에 임의로 수 ( 0 또는 INF 등)을 추가시켜서 PerfectBinary Tree로 만들어 줄것이다.
segment tree with sum query
BOJ 2042 - 구간 합 구하기
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t[4040400];
ll n;
void build(){
for(ll i = n-1;i>0;--i ) t[i] = t[i<<1] + t[i<<1 | 1];
}
void update(ll p, ll v){
for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = t[p] + t[p^1];
}
ll query(int l, int r){
ll res = 0;
for(l += n, r+= n; l<r;l>>=1, r>>= 1){
if(l&1) res += t[l++];
if(r&1) res += t[--r];
}
return res;
}
int main(void){
int N, M, K;
cin >> N >> M >> K;
n = 1;
while(n < N) n <<=1;
for(ll i = 0;i<N;i++) cin >> t[i+n];
build();
ll T = M+K;
while(T--){
ll a,b,c; cin >> a >> b >> c;
if(a&1) update(b-1,c);
else cout << query(b-1,c) << "\n";
}
}
segment tree with minimum
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9+1;
ll t[404040];
ll n;
void build(){
for(ll i = n-1;i>0;--i ) t[i] = min(t[i<<1], t[i<<1 | 1] );
}
void update(ll p, ll v){
for(t[p+=n] = v; p>1; p>>= 1) t[p>>1] = min(t[p], t[p^1] );
}
ll query(int l, int r){
ll res = INF;
for(l += n, r+= n; l<r;l>>=1, r>>= 1){
if(l&1) res = min(res, t[l++]);
if(r&1) res = min(res, t[--r]);
}
return res;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
n = 1;
while(n < N) n <<=1;
for(ll i = 0;i<N;i++) cin >> t[i+n];
for(ll i = 0; i<n;i++) t[i+n] = t[i+n] ? t[i+n] : INF;
build();
while(M--){
ll a,b; cin >> a >> b;
cout << query(a-1,b) << "\n";
}
}