[백준] No.11658 - 구간 합 구하기 3 (C++, 펜윅 트리)

문제

 

https://www.acmicpc.net/problem/11658

11658번: 구간 합 구하기 3

 

 

풀이

 

solved.ac 난이도: Platium 5

 

 

구간 합 문제 중에서도 중간에 값의 변경이 자주 일어나는 문제들은 세그먼트 트리 혹은 펜윅 트리를 통해 빠르게 해결할 수 있다.

 

해당 문제에는 두 가지 모두 적용 가능한데 2차원 세그먼트 트리로 코드를 작성하는 중에 repl.it에 오류가 계속 발생해서 2차원 펜윅 트리로 해결해 보았다.

펜윅 트리를 잘 모른다면 백준님의 게시글을 참조하자.

펜윅 트리 (바이너리 인덱스 트리) - Baekjoon Online Judge

 

2차원 펜위 트리의 구현을 위해 update함수는 테이블에서의 해당 숫자(num)의 위치 r, c를 이용하여 구현한다.

 

void update(int r, int c, int num){
  for(int row= r; row<=table_size ; row += (row & -row))
    for(int col = c; col<=table_size ; col +=(col & -col))
      tree[row][col] += num;    
}

 

tree의 각 row마다 포함관계를 갖는 col들을 update시켜준다.

백준님의 게시글에서 알 수 있듯이

col & -col의 값은 마지막 1의 위치를 나타낸다.

따라서 col +=(col & -col) 연산을 통해

그 수를 담당하는 한 단계 상위 구간을 나타낼 수 있다.

 

sum함수도 row마다 포함되는 column의 값들을 모두 더해주는 방식으로 구현한다.

 

int sum(int r, int c){
  int result=0;
  for(int row= r; row>0 ; row -= (row & -row))
    for(int col = c; col>0 ; col -=(col & -col))
      result += tree[row][col];
    
  return result;
}

 

sum 함수는 (1,1) ~ (1,c) + (2,1) ~ (2, c) + ... + (r,1) ~ (r,c)까지의 구간 합을 반환한다.

 

만약 (r1, c1)에서 (r2, c2)까지의 구간의 합만을 구하고 싶다면 추가적인 연산이 필요하다.

 

2차원 펜윅 트리에서 (r2,c2)가 포함하는 구간은 파란색으로 칠한 부분이다.

 

 

우리가 구하고 싶은 구간은 (r1, c1)에서 (r2, c2)까지인 빨간 구간이다.

 

따라서 파란 구간에서 빨간 구간을 제외한 구간의 합을 빼주어야 한다.

 

sum함수는 (1,1)에서 (r, c)까지의 구간합만을 반환해주므로

 

sum(r2, c2)에서 sum(r2, c1 -1), 와 sum(r1-1, c2)을

sum(r2, c1 -1)

sum (r1- 1 ,c2)

 

sum(r1-1, c1-1)

 

따라서 (r1, c1)에서 (r2, c2)까지의 구간의 합은 이와 같이 나타낼 수 있다.

sum(r2, c2) - sum(r2, c1-1) - sum(r1-1,c2) + sum(r1-1,c1-1)

 

 

 

코드