为整数数组优化 sum(i,j) 和 update(i,value)
Optimize sum(i,j) and update(i,value) for an arryas of integers
给定一个巨大的整数数组，优化函数 sum(i,j) 和 update(i,value)，使这两个函数的时间复杂度都小于 O(n)。
更新
这是一道面试题。我试过 O(n) sum(i,j) 和 O(1) update(i, value)。其他解决方案是将输入数组预处理为二维数组，为 sum(i,j) 提供 O(1) 答案。但这使得 O(n).
的更新功能
例如，给定一个数组：
A[] = {4,5,4,3,6,8,9,1,23,34,45,56,67,8,9,898,64,34,67,67,56,...}
要定义的操作是 sum(i,j) 和 update(i,value)。
sum(i,j) 给出从索引 i 到 j 的数字总和。update(i, value) 使用给定的 value.i 处的值
最直接的答案是 sum(i,j) 可以在 O(n) 时间内计算并在 O(1) 时间内更新 (i,value)。
第二种方法是预先计算 sum(i,j) 并将其存储在二维数组 SUM[n][n] 中，并在查询时在 O(1) 时间内给出答案。但是随后更新函数 update(i,value) 变为 O(n) 顺序，因为必须更新对应于索引 i 的整个 row/column。
面试官提示我做一些预处理和使用一些数据结构，但我想不到。
你需要的是线段树。线段树可以在 O(log(n)) 时间内执行 sum(i, j) 和 update(i, value)。
引自Wikipedia：
In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its structure cannot be modified once it is built.
树的叶子将是初始数组元素。他们的 parents 将是他们 children 的总和。例如：假设data[] = {2, 5, 4, 7, 8, 9, 5}，那么我们的树会是这样的：
这个树结构是用数组表示的。我们称这个数组为seg_tree。因此 seg_tree[] 的根将存储在数组的索引 1 处。两个 children 将存储在索引 2 和 3。1-indexed 表示的一般趋势将是：
- 索引
i 的左侧 child 位于索引 2*i。
- 索引
i 的右 child 位于索引 2*i+1。
索引 i 的 - Parent 位于索引
i/2.
和 0-indexed 表示：
- 索引
i 的左侧 child 位于索引 2*i+1。
- 索引
i 的右 child 位于索引 2*i+2.
索引 i 的 - Parent 位于索引
(i-1)/2.
上图中每个区间[i, j]表示区间data[i, j]中所有元素的和。根节点将表示整个数据的总和[]，即 sum(0, 6) 。它的两个children将表示sum(0, 3)和sum(4, 6)等等。
seg_tree[]、MAX_LEN的长度为（如果n = length of data[]):
2*n-1 当 n 是 2 的幂时2*(2^(log_2(n)+1) - 1 当 n 不是 2 的幂时。
从数据[]构建seg_tree[]:
在这种情况下，我们将假设一个 0-indexed 结构。索引 0 将是树的根，初始数组的元素将存储在叶子中。
data[0...(n-1)]是初始数组，seg_tree[0...MAX_LEN]是data[]的线段树表示。从伪代码中可以更容易理解如何构造树：
build(node, start, end) {
// invalid interval
if start > end:
return
// leaf nodes
if start == end:
tree[node] = data[start]
return
// build left and right subtrees
build(2*node+1, start, (start + end)/2);
build(2*node+2, 1+(start+end)/2, end);
// initialize the parent with the sum of its children
tree[node] = tree[2*node+1] + tree[2*node+2]
}
这里，
[start, end]表示data[]中要形成线段树表示的区间。最初，这是 (0, n-1).- node表示当前索引在seg_tree[].
我们通过调用 build(0, 0, n-1) 开始构建过程。第一个参数表示 seg_tree[] 中根的位置。第二个和第三个参数表示 data[] 中要形成线段树表示的区间。在随后的每个调用中，node 将代表 seg_tree[] 和 (start, end)[= 的索引230=] 将表示 seg_tree[node] 将存储总和的间隔。
分三种情况：
start > end 是一个无效的间隔，我们只是从这个调用中 return。 - 如果
start == end，表示seg_tree[]的叶子，因此，我们初始化tree[node] = data[start]
- 否则，我们处于不是叶子的有效区间。所以我们首先通过调用
build(node, start, (start + end)/2)构建这个节点的左child，然后通过调用build(node, 1+(start+end)/2, end)构建右子树。然后我们通过其child个节点的总和来初始化seg_tree[]中的当前索引。
总和(i, j):
我们需要检查节点的间隔是否与给定的间隔 (i, j) 重叠 (partial/complete) 或者它们根本不重叠。这是三种情况：
- 为了不重叠，我们可以简单地 return 0.
- 对于完全重叠，我们将 return 存储在该节点的值。
- 对于部分重叠，我们将同时访问 children 并递归地继续此检查。
假设我们需要找到sum(1, 5)的值。我们进行如下：
让我们使用一个空容器 (Q) 来存储感兴趣的区间。最终所有这些范围都将被它们 return 的值替换。最初，Q = {(0, 6)}.
我们注意到 (1, 5) 没有完全重叠 (0, 6)，所以我们删除这个范围并添加其 children 范围。
Q = {(0, 3), (4, 6)}
现在，(1, 5) 部分重叠 (0, 3)。所以我们删除 (0, 3) 并插入它的两个 children。 Q = {(0, 1), (2, 3), (4, 6)}
(1, 5) 与 (0, 1) 部分重叠，所以我们删除它并插入它的两个 child仁范围。 Q = {(0, 0), (1, 1), (2, 3), (4, 6)}
现在(1, 5)不与(0, 0)重叠，所以我们替换(0 , 0) 的值为 return （由于没有重叠，因此为 0）。 Q = {(0, (1, 1), (2, 3), (4, 6)}
接下来，(1, 5)与(1, 1)完全重叠，所以我们return存储的值在表示此范围的节点中（即 5）。 Q = {0, 5, (2, 3), (4, 6)}
接下来，(1, 5) 再次完全重叠 (2, 3)，所以我们 return 的值11.Q={0, 5, 11, (4, 6)}
接下来，(1, 5)部分verlaps (4, 6) 所以我们用它的两个 children 替换这个范围。 Q = {0, 5, 11, (4, 5), (6, 6)}
快进操作，我们注意到 (1, 5) 完全重叠 (4, 5) 所以我们用17和(1, 5)不重叠(6, 6)，所以我们用0代替。最后，Q = {0, 5, 11, 17, 0} .查询的答案是Q中所有元素的和，即33。
对于更新（i，值）：
对于update(i, value)，过程有些相似。首先我们将搜索范围(i, i)。我们在此路径中遇到的所有节点也需要更新。让change = (new_value - old_value)。然后在搜索 (i, i) 范围内遍历树时，我们会将此更改添加到除最后一个节点之外的所有节点，最后一个节点将简单地替换为新值。例如，让查询为 update(5, 8).
change = 8-9 = -1.
遇到的路径会是(0, 6) -> (4, 6) -> (4, 5) -> (5, 5).
(0, 6) = 40 + change = 40 - 1 = 39 的最终值。
(4, 6) = 22 + change = 22 - 1 = 21 的最终值。
(4, 5) = 17 + change = 17 - 1 = 16 的最终值。
(5, 5) = 8 的最终值。
最终的树将如下所示：
我们可以在 O(n) 时间内使用数组创建线段树表示，并且这两个操作的时间复杂度均为 O(log(n)).
一般线段树可以有效地执行以下操作：
- 更新：可以更新：
- 给定索引处的元素。
- 给定值区间内的所有元素。 Lazy Propagation 技术通常在这种情况下使用以实现效率。
- 查询：我们查询给定时间间隔内的某个值。几种基本类型的查询是：
- 区间中的最小元素
- 区间中的最大元素
- Sum/Product 一个区间内的所有元素
另一种数据结构Interval Tree也可以用来解决这个问题。推荐读物：
给定一个巨大的整数数组，优化函数 sum(i,j) 和 update(i,value)，使这两个函数的时间复杂度都小于 O(n)。
更新
这是一道面试题。我试过 O(n) sum(i,j) 和 O(1) update(i, value)。其他解决方案是将输入数组预处理为二维数组，为 sum(i,j) 提供 O(1) 答案。但这使得 O(n).
的更新功能例如，给定一个数组：
A[] = {4,5,4,3,6,8,9,1,23,34,45,56,67,8,9,898,64,34,67,67,56,...}
要定义的操作是 sum(i,j) 和 update(i,value)。
sum(i,j)给出从索引i到j的数字总和。update(i, value)使用给定的value. 更新索引
i 处的值
最直接的答案是 sum(i,j) 可以在 O(n) 时间内计算并在 O(1) 时间内更新 (i,value)。
第二种方法是预先计算 sum(i,j) 并将其存储在二维数组 SUM[n][n] 中，并在查询时在 O(1) 时间内给出答案。但是随后更新函数 update(i,value) 变为 O(n) 顺序，因为必须更新对应于索引 i 的整个 row/column。
面试官提示我做一些预处理和使用一些数据结构，但我想不到。
你需要的是线段树。线段树可以在 O(log(n)) 时间内执行 sum(i, j) 和 update(i, value)。
引自Wikipedia：
In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its structure cannot be modified once it is built.
树的叶子将是初始数组元素。他们的 parents 将是他们 children 的总和。例如：假设data[] = {2, 5, 4, 7, 8, 9, 5}，那么我们的树会是这样的：
这个树结构是用数组表示的。我们称这个数组为seg_tree。因此 seg_tree[] 的根将存储在数组的索引 1 处。两个 children 将存储在索引 2 和 3。1-indexed 表示的一般趋势将是：
- 索引
i的左侧 child 位于索引2*i。 - 索引
i的右 child 位于索引2*i+1。
索引 - Parent 位于索引
i/2.
i 的 和 0-indexed 表示：
- 索引
i的左侧 child 位于索引2*i+1。 - 索引
i的右 child 位于索引2*i+2.
索引 - Parent 位于索引
(i-1)/2.
i 的 上图中每个区间[i, j]表示区间data[i, j]中所有元素的和。根节点将表示整个数据的总和[]，即 sum(0, 6) 。它的两个children将表示sum(0, 3)和sum(4, 6)等等。
seg_tree[]、MAX_LEN的长度为（如果n = length of data[]):
2*n-1当 n 是 2 的幂时2*(2^(log_2(n)+1) - 1当 n 不是 2 的幂时。
从数据[]构建seg_tree[]:
在这种情况下，我们将假设一个 0-indexed 结构。索引 0 将是树的根，初始数组的元素将存储在叶子中。
data[0...(n-1)]是初始数组，seg_tree[0...MAX_LEN]是data[]的线段树表示。从伪代码中可以更容易理解如何构造树：
build(node, start, end) {
// invalid interval
if start > end:
return
// leaf nodes
if start == end:
tree[node] = data[start]
return
// build left and right subtrees
build(2*node+1, start, (start + end)/2);
build(2*node+2, 1+(start+end)/2, end);
// initialize the parent with the sum of its children
tree[node] = tree[2*node+1] + tree[2*node+2]
}
这里，
[start, end]表示data[]中要形成线段树表示的区间。最初，这是(0, n-1).- node表示当前索引在seg_tree[].
我们通过调用 build(0, 0, n-1) 开始构建过程。第一个参数表示 seg_tree[] 中根的位置。第二个和第三个参数表示 data[] 中要形成线段树表示的区间。在随后的每个调用中，node 将代表 seg_tree[] 和 (start, end)[= 的索引230=] 将表示 seg_tree[node] 将存储总和的间隔。
分三种情况：
start > end是一个无效的间隔，我们只是从这个调用中 return。- 如果
start == end，表示seg_tree[]的叶子，因此，我们初始化tree[node] = data[start] - 否则，我们处于不是叶子的有效区间。所以我们首先通过调用
build(node, start, (start + end)/2)构建这个节点的左child，然后通过调用build(node, 1+(start+end)/2, end)构建右子树。然后我们通过其child个节点的总和来初始化seg_tree[]中的当前索引。
总和(i, j):
我们需要检查节点的间隔是否与给定的间隔 (i, j) 重叠 (partial/complete) 或者它们根本不重叠。这是三种情况：
- 为了不重叠，我们可以简单地 return 0.
- 对于完全重叠，我们将 return 存储在该节点的值。
- 对于部分重叠，我们将同时访问 children 并递归地继续此检查。
假设我们需要找到sum(1, 5)的值。我们进行如下：
让我们使用一个空容器 (Q) 来存储感兴趣的区间。最终所有这些范围都将被它们 return 的值替换。最初，Q = {(0, 6)}.
我们注意到 (1, 5) 没有完全重叠 (0, 6)，所以我们删除这个范围并添加其 children 范围。
Q = {(0, 3), (4, 6)}
现在，(1, 5) 部分重叠 (0, 3)。所以我们删除 (0, 3) 并插入它的两个 children。 Q = {(0, 1), (2, 3), (4, 6)}
(1, 5) 与 (0, 1) 部分重叠，所以我们删除它并插入它的两个 child仁范围。 Q = {(0, 0), (1, 1), (2, 3), (4, 6)}
现在(1, 5)不与(0, 0)重叠，所以我们替换(0 , 0) 的值为 return （由于没有重叠，因此为 0）。 Q = {(0, (1, 1), (2, 3), (4, 6)}
接下来，(1, 5)与(1, 1)完全重叠，所以我们return存储的值在表示此范围的节点中（即 5）。 Q = {0, 5, (2, 3), (4, 6)}
接下来，(1, 5) 再次完全重叠 (2, 3)，所以我们 return 的值11.Q={0, 5, 11, (4, 6)}
接下来，(1, 5)部分verlaps (4, 6) 所以我们用它的两个 children 替换这个范围。 Q = {0, 5, 11, (4, 5), (6, 6)}
快进操作，我们注意到 (1, 5) 完全重叠 (4, 5) 所以我们用17和(1, 5)不重叠(6, 6)，所以我们用0代替。最后，Q = {0, 5, 11, 17, 0} .查询的答案是Q中所有元素的和，即33。
对于更新（i，值）：
对于update(i, value)，过程有些相似。首先我们将搜索范围(i, i)。我们在此路径中遇到的所有节点也需要更新。让change = (new_value - old_value)。然后在搜索 (i, i) 范围内遍历树时，我们会将此更改添加到除最后一个节点之外的所有节点，最后一个节点将简单地替换为新值。例如，让查询为 update(5, 8).
change = 8-9 = -1.
遇到的路径会是(0, 6) -> (4, 6) -> (4, 5) -> (5, 5).
(0, 6) = 40 + change = 40 - 1 = 39 的最终值。
(4, 6) = 22 + change = 22 - 1 = 21 的最终值。
(4, 5) = 17 + change = 17 - 1 = 16 的最终值。
(5, 5) = 8 的最终值。
最终的树将如下所示：
我们可以在 O(n) 时间内使用数组创建线段树表示，并且这两个操作的时间复杂度均为 O(log(n)).
一般线段树可以有效地执行以下操作：
- 更新：可以更新：
- 给定索引处的元素。
- 给定值区间内的所有元素。 Lazy Propagation 技术通常在这种情况下使用以实现效率。
- 查询：我们查询给定时间间隔内的某个值。几种基本类型的查询是：
- 区间中的最小元素
- 区间中的最大元素
- Sum/Product 一个区间内的所有元素
另一种数据结构Interval Tree也可以用来解决这个问题。推荐读物：