arrays - セグメント ツリーを使用して、指定された配列から最大合計部分配列を見つけます

Question

指定された配列から最大合計連続部分配列を見つけたかったのです。Kadane のアルゴリズムを使用した動的計画法の概念を使用して、最大和連続部分配列アプローチを見つける O(n) アプローチを知っています。

ただし、範囲クエリの数が非常に多い場合は、多くの時間がかかります。O（log（n））時間で解決する範囲クエリに回答するのに最適なオプションであるため、セグメントツリーを使用して解決する方法はありますか。ありがとうございました。

Answer 1

ジャスティンの答えに対する私のコメントによると、標準のセグメントツリーを拡張して、ツリーを構築するO(log(n))時間とともにクエリ時間を達成することができO(n log(n))ます。つまり、すべての n 要素をツリーに挿入します。

アイデアは、すべてのノードvに 1 つの値だけでなく 4 つの値を格納することです。

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]、考慮すべき簡単なケースがいくつかあります。

省略された詳細を理解していただければ幸いです。そうでない場合は、お知らせください。より詳細な説明をいたします。