スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Fenwick Tree の図

Fenwick Tree (Binary Indexed Tree ともいう) を勉強した。
とてもよい資料が web 上にいくつもあるのであえて解説を書くことはしないけど、考える際に作った図だけは載せておこうと思う。

Tags : アルゴリズム プログラミング

いくつかのサイトを見たところ、1-indexed (添え字を 1 から数える) で考えている人が多いのだけど、個人的には 0-indexed でないと気持ち悪いので 0-indexed で考えた。
bit 演算の式が変わる程度で、0-indexed でも 1-indexed でも考え方は同じ。

図は頂点数が 15 個のケース。
緑の丸が 1 つの頂点を表していて、中に書いてある数が頂点の番号。脇に書いてあるのが番号を 2 進数表記したもの。
Fenwick Tree では、頂点の番号は通りがけ順 (inorder) で付けていることになる。

† 素敵な資料たち。1 と 2 は 1-indexed で 3 は 0-indexed.
1. TopCoder Algorithm Tutorials
2. Algorithms of Python
3. Spaghetti Source
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。