フェンウィック木（Binary Indexed Tree）は部分和を保持し、1点の更新と接頭辞和の取得をそれぞれO(log N)時間で行います。元の値は別の配列に保存します。1-based index iの値がoldからnewに変わったら、その差new - oldを木のindex iに加算します。
1-based index 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();
}
}
}