Description

给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。

Examples

1
2
3
4
5
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Thought

Segement Tree(线段树)

一颗线段树的构造就是根据区间的性质的来构造的, 如下是一棵区间[0, 3]的线段树,每个[start, end]都是一个二叉树中的节点。

graph TD;
	A["[0,3]"] --> B["[0,1]"];
	A["[0,3]"] --> C["[2,3]"];
	B --> D["[0,0]"];
	B --> E["[1,1]"];
	C --> F["[2,2]"];
	C --> G["[3,3]"];

区间划分大概就是上述的区间划分。可以看出每次都将区间的长度一分为二,数列长度为n,所以线段树的高度是log(n),这是很多高效操作的基础。
上述的区间存储的只是区间的左右边界。我们可以将区间的最大值加入进来,也就是树中的Node需要存储leftright左右子节点外,还需要存储start, end, val区间的范围和区间内表示的值。

可以储存不同的值,例如区间内的最大值,最小值,区间的求和等等。

因为每次将区间的长度一分为二,所有创造的节点个数,即底层有n个节点,那么倒数第二次约n/2个节点,倒数第三次约n/4个节点,依次类推:

1
2
3
n + 1/2 * n + 1/4 * n + 1/8 * n + ...
= (1 + 1/2 + 1/4 + 1/8 + ...) * n
= 2n

所以构造线段树的时间复杂度和空间复杂度都为O(n)

Solution

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
class segmentTree{
constructor(start,end,sum){
this.start = start;
this.end = end;
this.sum = sum;
this.left = this.right = null;
}
}
var NumArray = function(nums) {
// console.log(nums.length);
this.segmentTree = build(0,nums.length-1,nums);
};

var build = function(left,right,array){
if(left > right){
return null;
}

let root = new segmentTree(left,right,array[left]);
if(left === right){
return root;
}
let mid = Math.floor((left+right)/2);
root.left = build(left,mid,array);
root.right = build(mid+1,right,array);
root.sum = root.left.sum+root.right.sum;
return root;
}

NumArray.prototype.update = function(i,val) {
modify(this.segmentTree,i,val);
};

var modify = function(root,index,value){
if(root.start == index && root.end == index){
root.sum = value;
return;
}

let mid = Math.floor((root.start+root.end)/2);
if(index<=mid){
modify(root.left,index,value);
}else{
modify(root.right,index,value);
}

root.sum = root.left.sum+root.right.sum;
}
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i,j) {
console.log(this.segmentTree);
let res = query(this.segmentTree,i,j);
return res;
};

var query = function(root,start,end){
if(start == root.start && root.end == end){
return root.sum;
}

let mid = Math.floor((root.start+root.end)/2);
let leftsum=0;
let rightsum=0;
//左子区
if(mid >= start){
if(mid<end){
leftsum = query(root.left,start,mid);
}else{
leftsum = query(root.left,start,end);
}
}
//右子区
if(mid<end){
if(start <= mid){
rightsum = query(root.right,mid+1,end);
}else{
rightsum = query(root.right,start,end);
}
}

return leftsum+rightsum;
}