이거때매 하루종일 고생중. x&(-x)가 무엇이냐 부터 힘들었다.
read 연산
1 2 3 4 5 6 7 8 9 | int read(int idx)
{
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
|
update 연산
1 2 3 4 5 6 7 8 9 | int tree[20];
#define MaxVal 16
void update(int idx ,int val)
{
while (idx <= MaxVal){
tree[idx] += val;
idx += (idx & -idx);
}
}
|
일단 read가 처음부터 idx까지의 구간 합을 구하는 함수고
update는 idx번째 아이템의 값을 갱신하는 함수이다. 이렇게 되면
read도 log(n), update도 log(n)으로 쿼리가 m개면 m*log(n)으로 해결 된다.
여기서 idx를 갱신할 때 2가지 방법을 쓸 수 있다.
1. x&(-x)
이것은 x의 약수 중 2의 제곱수만 빼면 된다. ex) 4 : 4, 5 : 1, 6 : 2
그러므로 idx -= (idx& -idx) 이런식.
2. x&(x-1)
이것은 x 이하의 수 중 가장 큰 2의 배수를 리턴. ex) 4 : 4, 5 : 4, 6 : 6, 15 : 14
그러므로 idx = (idx&(idx-1))
참고 사이트 : http://59.23.113.171/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree
예제 문제 : https://www.acmicpc.net/problem/2042 - 구간 합치기
가장 전형적인 문제로 BIT를 '사용하기만하면' 풀어진다.
아래는 위 문제의 소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <stdio.h>
long long int tr[1000001];
long long int val[1000001];
int n;
long long int read(long long int idx){
long long int sum = 0;
while (idx > 0){
sum += tr[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(long long int idx ,long long int val){
while (idx <= n){
tr[idx] += val;
idx += (idx & -idx);
}
}
int main(){
int m,k;
scanf("%d %d %d",&n,&m,&k);
for(long long int i=1;i<=n;i++){
scanf("%lld",&val[i]);
update(i,val[i]);
}
for(int i=0;i<m+k;i++){
long long int a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
if(a==1){
update(b,c-val[b]);
val[b] = c;
}
else{
printf("%lld\n",read(c)-read(b-1));
}
}
return 0;
}
|
