키흐

 이거때매 하루종일 고생중. x&(-x)가 무엇이냐 부터 힘들었다.

read 연산

int read(int idx)
{
   int sum = 0;
   while (idx > 0){
      sum += tree[idx];
      idx -= (idx & -idx);
   }
   return sum;
}

update 연산

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를 '사용하기만하면' 풀어진다.

아래는 위 문제의 소스코드

#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;
}