문제
N개의 정수로 이루어진 배열이 있다. Q개의 쿼리가 주어지며, 각 쿼리는 4개의 정수 x, y, a, b로 이루어진다.
x번째부터y번째까지의 합을 출력한다 (x, y 순서는 랜덤).a번째 값을b로 변경한다.
입력
첫 번째 줄에 N과 Q가 주어진다. (1 ≤ N, Q ≤ 100,000)
두 번째 줄에 N개의 정수가 주어진다. (각 값의 절댓값 ≤ 2^31 - 1)
이후 Q줄에 걸쳐 x, y, a, b가 주어진다.
출력
각 쿼리에서 x번째부터 y번째까지의 합을 출력한다.
예제
5 2
1 2 3 4 5
2 3 3 7
1 5 1 3출력:
5
22풀이
핵심 아이디어: 구간 합 쿼리와 점 업데이트를 O(log N)으로 처리하는 펜윅 트리(Binary Indexed Tree, BIT)를 사용한다. 세그먼트 트리보다 구현이 간단하고 메모리 효율적이다. 펜윅 트리는 비트 연산으로 부모/자식 노드를 빠르게 탐색한다.
- 배열을 1-indexed로 읽으면서
update(i, arr[i])로 펜윅 트리를 초기화한다. - 각 쿼리에서
min(x,y)~max(x,y)구간 합을prefixSum(end) - prefixSum(start-1)로 계산한다. a번째 값을b로 변경할 때는update(a, b - arr[a])로 차이만큼 갱신하고arr[a] = b를 유지한다.prefixSum(i):i -= (i & -i)로 부모 노드를 탐색하며 누적합 계산.update(i, dif):i += (i & -i)로 관련 노드를 모두 갱신.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day318BOJ1275커피숍 {
static int N, Q;
static long arr[], tree[];
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
arr = new long[N + 1];
tree = new long[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Long.parseLong(st.nextToken());
update(i, arr[i]);
}
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(intervalSum(Math.min(x, y), Math.max(x, y))).append("\n");
update(a, b - arr[a]);
arr[a] = b;
}
System.out.println(sb.toString());
}
static long prefixSum(int i) {
long result = 0;
while (i > 0) {
result += tree[i];
i -= (i & -i);
}
return result;
}
static void update(int i, long dif) {
while (i <= N) {
tree[i] += dif;
i += (i & -i);
}
}
static long intervalSum(int start, int end) {
return prefixSum(end) - prefixSum(start - 1);
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)