我想从给定的数组中找到最大的和连续子数组。我知道使用 Kadane 算法的动态编程概念找到最大和连续子数组方法的 O(n) 方法。
但是如果范围查询的数量非常大,这将花费很多时间。有没有办法使用 Segment-Trees 来解决它,因为它是回答它在 O(log(n)) 时间内解决的范围查询的最佳选择。谢谢你。
我想从给定的数组中找到最大的和连续子数组。我知道使用 Kadane 算法的动态编程概念找到最大和连续子数组方法的 O(n) 方法。
但是如果范围查询的数量非常大,这将花费很多时间。有没有办法使用 Segment-Trees 来解决它,因为它是回答它在 O(log(n)) 时间内解决的范围查询的最佳选择。谢谢你。
根据我对贾斯汀回答的评论,您可以增加标准段树以实现O(log(n))
查询时间随着O(n log(n))
时间的推移来构建树,即将所有 n 元素插入树中。
这个想法是在每个节点中存储的v
不仅仅是一个值,而是四个:
- max_value[v] := v`s 子树中的最大连续和
- left_value[v] := 与 v 的子树对应的范围左边界相邻的最大连续和
- right_value[v] := 与 v 的子树对应的范围右边界相邻的最大连续和
- sum[v] := v 的子树中所有元素的总和
为了对节点执行更新操作v
,您必须重新计算max_value[v], left_value[v], right_value[v], sum[v]
。这非常简单,我认为您可以自己解决 - 有几个案例需要考虑。
查询操作类似于基本段树中的查询操作。唯一的区别是,在这种情况下,您还必须考虑计算结果left_value[v]
的时间和right_value[v]
时间 - 同样,有一些简单的情况需要考虑。
我希望你能找出省略的细节。如果没有,请告诉我,我会给出更详细的解释。
While @pkacprzak's answer describes the solution well, some people might prefer a code example.
#include <iostream>
#define ll long long
using namespace std;
const int N=1<<17; // big power of 2 that fits your data
int n,k;
struct P {ll l, r, ts, bs;}; // left, right, totalsum, bestsum
P p[2*N];
ll maxf(ll a,ll b,ll c) {return max(a,max(b,c));}
P combine(P &cl,P &cr) {
P node;
node.ts = cl.ts + cr.ts;
node.l = maxf(cl.l, cl.ts, cl.ts + cr.l);
node.r = maxf(cr.r, cr.ts, cr.ts + cl.r);
node.bs = maxf(cl.bs, cr.bs, cl.r + cr.l);
return node;
}
void change(int k, ll x) {
k += N;
p[k].l = p[k].r = p[k].ts = p[k].bs = x;
for (k /= 2; k >= 1; k /= 2) {
p[k] = combine(p[2*k], p[2*k+1]);
}
}
To add/change values in the segment tree use change(k, x)
(O(log(n))
per call) where k is the position and x is the value. The maximum subarray's sum can be read from p[1].bs
(top of the tree) after each call to change
.
If you also need to find the exact indices of the subarray, you can do a recursive top-down query in O(log(n))
or a binary search of O(log^2(n))
with an iterative query.
EDIT: if we are interested in the maximum subarray of a given subarray, it's best to build a recursive top-down query. See:
https://www.quora.com/How-do-I-calculate-the-maximum-sub-segment-sum-in-a-segment-tree
So to recap, segment trees can handle this problem with changes to the data and with changes to the range we are interested in.