简介
如果我们已知一个数组，我们接下来有一些操作：在数组的范围中查找最大值或最小值或和，然后更新数组中的某个值，如何才能让这一系列的操作的时间复杂度更小呢？
- 第一种就是每次查找使都在范围中遍历一遍，更新时只更新数组中的值，即查找 O(n)，更新 O(1)
- 另一种就是通过线段数组，使得查找 O(logn)，更新 O(logn)
设计思路
将整个数组转为树型表示，叶子节点为数组，其他节点为此根下范围的记录，例如记录下此范围的最小值，最大值，和等
在查询时只要根据范围找到相应根就能找到结果，在更新时，更新完叶子节点后也要同步跟新所在范围的根节点
代码模板
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
|
// 通过范围求和
class SegmentTree {
int[] tree; // tree 为压缩的树
int n;
public void SegmentTree(int[] nums) {
n = nums.length;
tree = new int[2 * n]; // tree[1] 为根节点
for (int i = 0; i < n; i++) {
tree[i + n] = nums[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
public void update(int index, int val) {
int pos = n + index;
tree[pos] = val;
while (pos > 0) {
int left = pos % 2 == 0 ? pos : pos - 1;
int right = pos % 2 == 0 ? pos + 1, pos;
tree[pos/2] = tree[left] + tree[right];
pos /= 2;
}
}
public void search(int left, int right) {
int sum = 0;
left += n;
right += n;
while (r >= l) {
if (l % 2 == 1) {
// 左边为一个区间
sum += tree[l];
l++;
}
if (r % 2 == 0) {
// 右边部分为一个区间
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
|
例题
LC 307. 区域和检索 - 数组可修改
给你一个数组 nums ，请你完成两类查询。
- 其中一类查询要求 更新 数组
nums 下标对应的值
- 另一类查询要求返回数组
nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]
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
|
class NumArray {
SegmentTree sTree;
public NumArray(int[] nums) {
sTree = new SegmentTree(nums);
}
public void update(int index, int val) {
sTree.update(index, val);
}
public int sumRange(int left, int right) {
return sTree.search(left, right);
}
}
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[n * 2];
for (int i = 0; i < n; i++) {
tree[i + n] = nums[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
public void update(int index, int val) {
index += n;
tree[index] = val;
while (index > 0) {
int l = index % 2 == 0 ? index : index - 1;
int r = index % 2 == 0 ? index + 1 : index;
tree[index / 2] = tree[l] + tree[r];
index /= 2;
}
}
public int search(int l, int r) {
int sum = 0;
l += n;
r += n;
while (l <= r) {
if (l % 2 != 0) {
sum += tree[l];
l++;
}
if (r % 2 == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
|