leetcode 307 区域和检索线段树(基本无lazy）

 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  */
每天进步一点点~
leetcode 307 区域和检索 线段树(基本 无lazy）

leetcode 307 区域和检索线段树(基本无lazy）
