펜윅 트리(이진 인덱스 트리)는 부분 합을 저장하여 한 원소의 변경과 구간의 접두 합 조회를 각각 O(log N) 시간에 처리합니다. 원본 값은 별도로 보관합니다. 1-based 인덱스 i의 값이 old에서 new로 바뀌면 차이 new - old를 트리의 인덱스 i에 더합니다.
1-based 인덱스 i에서 i & -i는 가장 낮은 비트 하나를 추출합니다. 접두 합을 구할 때는 이 값을 반복해서 빼며 겹치지 않는 블록으로 이동하고, 값을 갱신할 때는 반복해서 더하며 해당 값을 포함하는 모든 블록을 방문합니다. a부터 b까지의 합은 prefix(b) - prefix(a - 1)입니다. 초기 노드를 부모 노드에 전파해 트리를 만들면 O(N) 시간이 걸립니다. 변경과 조회는 각각 O(log N) 시간이며, 값 배열과 트리가 사용하는 공간은 O(N)입니다. 원소와 누적 합을 저장하기 위해 long을 사용합니다.
Java
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int updateCount = input.nextInt();
int queryCount = input.nextInt();
long[] values = new long[n];
for (int i = 0; i < n; i++) {
values[i] = input.nextLong();
}
FenwickTree tree = new FenwickTree(values);
StringBuilder output = new StringBuilder();
for (int i = 0; i < updateCount + queryCount; i++) {
int type = input.nextInt();
int a = input.nextInt();
long b = input.nextLong();
if (type == 1) {
int index = a - 1;
long delta = b - values[index];
values[index] = b;
tree.add(a, delta);
} else {
output.append(tree.prefixSum((int) b) - tree.prefixSum(a - 1)).append('\n');
}
}
System.out.print(output);
}
private static final class FenwickTree {
private final long[] tree;
FenwickTree(long[] values) {
tree = new long[values.length + 1];
for (int i = 1; i < tree.length; i++) {
tree[i] += values[i - 1];
int parent = i + (i & -i);
if (parent < tree.length) {
tree[parent] += tree[i];
}
}
}
void add(int index, long delta) {
for (int i = index; i < tree.length; i += i & -i) {
tree[i] += delta;
}
}
long prefixSum(int index) {
long sum = 0;
for (int i = index; i > 0; i -= i & -i) {
sum += tree[i];
}
return sum;
}
}
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
boolean negative = c == '-';
if (negative) {
c = read();
}
long value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return negative ? -value : value;
}
int nextInt() throws IOException {
return (int) nextLong();
}
}
}