线段树
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
class NumArray {
int[] segmentTree;
int n;
public NumArray(int[] nums) {
n = nums.length;
segmentTree = new int [2 * n];
System.arraycopy(nums, 0, segmentTree, n, n);
for(int i = n - 1; i > 0; i--){
segmentTree[i] = segmentTree[2 * i] + segmentTree[2 * i + 1];
}
}
public void update(int index, int val) {
index += n;
segmentTree[index] = val;
index /= 2;
while(index != 0){
segmentTree[index] = segmentTree[2 * index] + segmentTree[2 * index + 1];
index /= 2;
}
}
public int sumRange(int left, int right) {
left += n;
right += n;
int sum = 0;
while(left <= right){
if(left % 2 == 1){
sum += segmentTree[left];
left ++;
}
if(right % 2 == 0){
sum += segmentTree[right];
right--;
}
left /= 2;
right /= 2;
}
return sum;
}
}