백준: Class 6 - 2042, 11505(세그먼트 트리)
</br>
2042: 구간 합 구하기를 보니, 자료 구조 시간 때 세그먼트 트리를 봤던 게 기억이 났다
구현은 할 줄 모르므로 한 번 정리하고 가자
</br>
Segment Tree
long long makeSeg(int a, int b, int now){
if( a == b ) return segtree[now] = nums[a];
int mid = (a+b) / 2;
segtree[now] = makeSeg(a, mid, now*2) + makeSeg(mid+1, b, now*2+1);
return segtree[now];
}
맨 처음, 세그먼트 트리를 만드는 재귀 함수다.
원본 배열은 0부터 시작하고, 세그먼트 트리는 1부터 시작한다고 보자
만약 현재 인덱스의 처음과 끝이 같으면 세그먼트 트리의 현재 노드에 값을 넣는다.
그다음 반띵해서, 재귀 돌린다. 앞 부분은 그냥 *2, 뒷 부분은 +1이 붙는 걸 기억하면 된다
long long sumSeg(int a, int b, int now, int l, int r){
if( r < a || b < l ) return 0;
if( l <= a && b <= r ) return segtree[now];
int mid = (a+b) / 2;
return sumSeg(a, mid, now*2, l, r) + sumSeg(mid+1, b, now*2+1, l, r);
}
구간 합을 구할 때 쓰는 재귀 함수다.
만약 구할 구간이 현재 인덱스 밖에 있다면 더할 필요 없으므로 return 0 한다.
안에 있다면, 세그먼트 트리 값을 리턴하면 된다.
그게 아니면, 또 반띵해서 찾아 주면 된다
구간은 고정되어 있으므로 외우기 편하다
void updateSeg(int a, int b, int now, int ind, long long change){
if( ind < a || b < ind ) return;
segtree[now] += change;
if( a == b ) return;
int mid = (a+b) / 2;
updateSeg(a, mid, now*2, ind, change);
updateSeg(mid+1, b, now*2+1, ind, change);
}
업데이트할 때 쓰는 재귀 함수다.
바꿀 부분이 현재 인덱스의 밖에 있으면 바꿀 게 없으므로 그냥 리턴한다.
그게 아니면, 바뀐 만큼 세그먼트 트리에 더해 준다.
그리고 현재 인덱스가 같지 않으면 또 반띵해서 돌려 준다.
int h = ceil(log2(n));
segtree.assign(1<<(h+1), 0);
makeSeg(0, n-1, 1);
long long change = val - nums[b];
updateSeg(0, n-1, 1, b, change);
nums[b] = c;
cout << sumSeg(0, n-1, 1, b, c) << '\n';
트리의 높이를 int h = ceil(log2(n))라 하면, 세그먼트 트리의 최대 크기는 2^(h+1)이 된다. 이렇게 할당하면 메모리를 좀 아낄 수 있겠지
업데이트를 할 때는, next - prev를 인자로 넘기고, 세그먼트 트리에 그 값을 더해주며 업데이트 한다. 그리고 나서 원본 배열도 꼭 업데이트 해 줘야 한다!!
b~c의 합은 그대로 b, c를 인자로 넣어 주면 된다.
</br>
2042: 구간 합 구하기
https://www.acmicpc.net/problem/2042
#include <bits/stdc++.h>
using namespace std;
long long nums[1000001];
vector<long long> segtree;
long long makeSeg(int a, int b, int now){
if( a == b ) return segtree[now] = nums[a];
int mid = (a+b) / 2;
segtree[now] = makeSeg(a, mid, now*2) + makeSeg(mid+1, b, now*2+1);
return segtree[now];
}
long long sumSeg(int a, int b, int now, int l, int r){
if( r < a || b < l ) return 0;
if( l <= a && b <= r ) return segtree[now];
int mid = (a+b) / 2;
return sumSeg(a, mid, now*2, l, r) + sumSeg(mid+1, b, now*2+1, l, r);
}
void updateSeg(int a, int b, int now, int ind, long long change){
if( ind < a || b < ind ) return;
segtree[now] += change;
if( a == b ) return;
int mid = (a+b) / 2;
updateSeg(a, mid, now*2, ind, change);
updateSeg(mid+1, b, now*2+1, ind, change);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> nums[i];
}
int h = ceil(log2(n));
segtree.assign(1<<(h+1), 0);
makeSeg(0, n-1, 1);
m += k;
while( m-- ){
long long a, b, c;
cin >> a >> b >> c;
b--;
if( a == 1 ){
long long change = c - nums[b];
updateSeg(0, n-1, 1, b, change);
nums[b] = c;
}
else cout << sumSeg(0, n-1, 1, b, c-1) << '\n';
}
}
자꾸 틀렸는데, sumSeg()에 인자를 넘겨 줄 때 b는 b--를 해 줬는데 c는 인덱스가 하나 큰 걸 까먹었기 때문에… 조심합시다
</br>
11505: 구간 곱 구하기
https://www.acmicpc.net/problem/11505
#include <bits/stdc++.h>
#define MAX 1000000007
using namespace std;
long long nums[1000001];
vector<long long> segtree;
long long makeSeg(int a, int b, int now){
if( a == b ) return segtree[now] = nums[a];
int mid = (a+b) / 2;
segtree[now] = makeSeg(a, mid, now*2) * makeSeg(mid+1, b, now*2+1);
segtree[now] %= MAX;
return segtree[now];
}
long long sumSeg(int a, int b, int now, int l, int r){
if( r < a || b < l ) return 1;
if( l <= a && b <= r ) return segtree[now];
int mid = (a+b) / 2;
long long s1 = sumSeg(a, mid, now*2, l, r) % MAX;
long long s2 = sumSeg(mid+1, b, now*2+1, l, r) % MAX;
return (s1 * s2) % MAX;
}
long long updateSeg(int a, int b, int now, int ind, long long val){
if( ind < a || b < ind ) return segtree[now];
if( a == b ) return segtree[now] = val;
int mid = (a+b) / 2;
long long u1 = updateSeg(a, mid, now*2, ind, val);
long long u2 = updateSeg(mid+1, b, now*2+1, ind, val);
return segtree[now] = (u1*u2) % MAX;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> nums[i];
}
int h = ceil(log2(n));
segtree.assign(1<<(h+1), 1);
makeSeg(0, n-1, 1);
m += k;
while( m-- ){
long long a, b, c;
cin >> a >> b >> c;
b--;
if( a == 1 ) updateSeg(0, n-1, 1, b, c);
else cout << sumSeg(0, n-1, 1, b, c-1) << '\n';
}
}
updateSeg() 부분이 바뀐다.
구간 합에서처럼 바뀌는 만큼만 곱해서 업데이트 하려 했더니, 막 0이 됐다가 1이 됐다가 뭐가 됐다가 하면 값이 꼬이기 때문에… 다시 리프부터 트리를 만들어준다는 느낌이라서 makeSeg()와 거의 유사하게 작동한다
이렇게 보니 makeSeg()랑 updateSeg()를 합쳐도 될 듯
</br>
외우기 편하긴 한데 은근 까다롭다
</br>
댓글남기기