[백준] 2042: 구간 합 구하기 - JS (펜윅트리(BIT))

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

펜윅 트리는 구간 합을 구하는 것에 특화되어 있는 자료구조 이다.

펜윅 트리를 구성하는 메서드는 update 와 sum 메서드 이다. 

 

 

update

// x: 업데이트 하는 인덱스, diff: 원래 값과 바뀐 값의 차이

• 인자: x, diff
• 조건: x <= N
• 동작: 인자로 들어온 x 에서 x & -x 를 더해주면 해당 인덱스가 영향을 주는 다음 인덱스를 찾아갈 수 있다.

 

 

sum

• 인자: x
• 조건: x > 0
• 동작: 인자로 들어온 x 에서 x & -x 를 빼주고 반복하면 1 부터 x 까지의 합을 구할 수 있다.

 

구간 합은 sum(b) - sum(a - 1) 을 해주면 구할 수 있다.

 

 

예시 배열(arr)과 펜윅 트리(ft)

 

 

세그먼트 트리 보다는 구현이 쉬웠는데 범용성이 아쉽다. 구간 합 문제에서 편하게 사용할 수 있을 것 같다.

 

 

 

펜윅 트리를 구현하며 배운 것들

펜윅 트리를 위한 글에서 캡쳐하였다.

 

 

 

 

 

 

  풀이

 

class FenwickTree {
	// N: 요소 개수
	constructor(N){
		this.N = N;
		this.tree = new BigInt64Array(this.N+1).fill(0n)
  }

	// index: 변경 된 인덱스, diff: 원래 값과 현재 값의 차이
	update(index, diff){
		while(index <= this.N){
			this.tree[index] += BigInt(diff);
			index += index & -index;
		}
	}

	// sum 메서드: 1부터 index 까지의 합을 구하고 반환함
	sum(index){
		let result = 0n;
		while(index > 0){
			result += this.tree[index];
			index -= index & -index;
		}
		return result
	}
}

let input = require('fs').readFileSync(	'/dev/stdin' ).toString().trim().split('\n');

const [N, M, K] = input[0].split(" ").map(Number);

const arr = new BigInt64Array(N + 1);

// 입력값
for(let i = 1; i <= N; i++){
	arr[i] = BigInt(input[i]);
}

const ft = new FenwickTree(N)

// 초기화(initializing)
for(let i = 1; i <= N; i++){
  ft.update(i, arr[i])
}

let answer = "";

for(let i = N + 1; i < N+M+K+1; i++){
  const [a, b, c] = input[i].split(" ");

  if(Number(a) == 1){
    const diff = BigInt(c) - arr[b]
    arr[b] = BigInt(c)
    ft.update(Number(b), diff)
  } else {
    answer += `${ft.sum(Number(c)) - ft.sum(Number(b) - 1)}\n`
  }
}

console.log(answer)