問題タブ [fenwick-tree]

今日、フェンウィック ツリー (バイナリ インデックス ツリー) についての講義を聞きました。先生は、このツリーは区間ツリーとセグメント ツリーの一般化であると言いましたが、この 3 つのデータ構造の実装は異なります。この断言は本当ですか？なぜ？

Fenwick Tree（またはBinary Indexed Tree）を次のように変更できるかどうか疑問に思いました。

1）範囲内のすべての要素の周波数を特定の量だけ増加させます

2）単一要素の頻度を照会します。

これは、更新が単一の要素で実行され、クエリが範囲全体で実行される従来のフェンウィックツリーとは対照的です（逆フェンウィックツリーのようなものです）。

私は 3 次元のフェンウィック ツリーデータ構造を持っています。(x0, y0, z0)からまでのセグメントの合計を計算する必要があります(x, y, z)

包含と排除の公式は何ですか? たとえば、2D バリアントの場合は

前もって感謝します

http://www.comp.nus.edu.sg/~stevenha/ft.pdf

2D の場合は次のとおりです。

最近、Fenwick Tree (Binary Indexed Tree)データ構造について学びました。

クエリを実行すると、(idx & -idx) を減算する理由が理解できます。ただし、値を更新するときに (idx & -idx) を追加する理由がよくわかりません。

言い換えれば、単一の要素 x を更新することによって影響を受けるすべての間隔を更新する必要があることはわかっています。また、BIT[x] が最初に更新されることはわかっていますが、次のインデックスが更新される理由を理解できません。ビット[x + (x & -x)]

ありがとう。

バイナリ インデックス ツリー (BIT) を使用して、特定の長さの増加するサブシーケンスの総数を見つけるにはどうすればよいですか?

実はこれはSpoj Online Judgeからの問題です

例
配列があるとします1,2,2,10

長さ 3 の増加するサブシーケンスは1,2,4、1,3,4

したがって、答えは2です。

フェンウィック木を使用して、配列内の非減少サブシーケンスの最大和を見つけるにはどうすればよいですか? たとえば、1 4 4 2 2 3 3 1 がある場合、非減少サブシーケンスの最大合計は 11 (1 2 2 3 3) です。

誰でもこのタスクを手伝ってもらえますかhttp://www.spoj.com/problems/INVCNT/。最初はビットウェイで考えようとしますが、できません。このタスクの解決策を BIT で説明できる人はいますか。ビット - バイナリ インデックス付きツリー c++

kthフェンウィック ツリーで最小の実際の周波数を時間内に見つけることを意味しますO(k log(n))。
私のデータが次の場合:

したがって、2 番目に小さい要素はインデックス 1 になります。