1 class NumArray {
2 int MAXN;
3 int[] sum;
4 int[] arr;
5
6 public NumArray(int[] nums) {
7 this.arr = nums;
8 MAXN = nums.length << 2;//4倍空间
9 sum = new int[MAXN];
10 build(0, arr.length - 1, 1);
11 }
12
13 private void build(int l, int r, int rt) {
14 if (l == r) {
15 sum[rt] = arr[l];
16 return;
17 }
18 int mid = l + ((r - l) >> 1);
19 build(l, mid, rt << 1);
20 build(mid + 1, r, rt << 1 | 1);
21 pushUp(rt, rt << 1, rt << 1 | 1);
22 }
23
24 private void pushUp(int rt, int lc, int rc) {
25 sum[rt] = sum[lc] + sum[rc];
26 }
27
28 //nums[index] to val,本题只有单个位置的更新，所以不用维护更新表
29 public void update(int index, int val) {
30 update(index, index, val, 0, arr.length - 1, 1);
31 }
32
33 private void update(int l, int r, int C, int L, int R, int rt) {
34 if (l <= L && r >= R) {//必定是l==L==R==r
35 sum[rt] = C;
36 return;
37 }
38 //下发任务
39 int mid = L + ((R - L) >> 1);
40 if (l <= mid) {
41 update(l, r, C, L, mid, rt << 1);
42 }
43 if (r > mid) {
44 update(l, r, C, mid + 1, R, rt << 1 | 1);
45 }
46 pushUp(rt, rt << 1, rt << 1 | 1);
47 }
48
49
50 public int sumRange(int left, int right) {
51 return query(left, right, 0, arr.length - 1, 1);
52 }
53
54 private int query(int l, int r, int L, int R, int rt) {
55 if (l <= L && r >= R) {
56 return sum[rt];
57 }
58 //任务下发
59 int mid = L + ((R - L) >> 1);
60 int ans = 0;
61 if (l <= mid) {
62 ans += query(l, r, L, mid, rt << 1);
63 }
64 if (r > mid) {
65 ans += query(l, r, mid + 1, R, rt << 1 | 1);
66 }
67 pushUp(rt,rt<<1,rt<<1|1);//沿途没有懒着的任务，所以每次更新完整个线段树所有节点的值都是正确的，这里都不用pushUp了
68 return ans;
69 }
70 }
71
72 /**
73 * Your NumArray object will be instantiated and called as such:
74 * NumArray obj = new NumArray(nums);
75 * obj.update(index,val);
76 * int param_2 = obj.sumRange(left,right);
77 */
