arrays - 使用段树从给定数组中找到最大和子数组

Question

我想从给定的数组中找到最大的和连续子数组。我知道使用 Kadane 算法的动态编程概念找到最大和连续子数组方法的 O(n) 方法。

但是如果范围查询的数量非常大，这将花费很多时间。有没有办法使用 Segment-Trees 来解决它，因为它是回答它在 O(log(n)) 时间内解决的范围查询的最佳选择。谢谢你。

Answer 1

根据我对贾斯汀回答的评论，您可以增加标准段树以实现O(log(n))查询时间随着O(n log(n))时间的推移来构建树，即将所有 n 元素插入树中。

这个想法是在每个节点中存储的v不仅仅是一个值，而是四个：

1. max_value[v] := v`s 子树中的最大连续和
2. left_value[v] := 与 v 的子树对应的范围左边界相邻的最大连续和
3. right_value[v] := 与 v 的子树对应的范围右边界相邻的最大连续和
4. sum[v] := v 的子树中所有元素的总和

为了对节点执行更新操作v，您必须重新计算max_value[v], left_value[v], right_value[v], sum[v]。这非常简单，我认为您可以自己解决 - 有几个案例需要考虑。

查询操作类似于基本段树中的查询操作。唯一的区别是，在这种情况下，您还必须考虑计算结果left_value[v]的时间和right_value[v]时间 - 同样，有一些简单的情况需要考虑。

我希望你能找出省略的细节。如果没有，请告诉我，我会给出更详细的解释。

Answer 2

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.