ForHosting KIT · 開発者向けツール

Fenwick木インデックス計算

添字を入力すると、Fenwick木の中でどう移動するかが分かります。13は2進数で1101、最下位ビットは1で、更新では14へ、和の計算では12へ進みます。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

添字: 13
サイズ: 16

結果

最下位のセットビット: 1
更新の次のインデックス: 14
クエリの親: 12
2進数: 0b1101

Fenwick木（binary indexed tree）は、長さが2の累乗である部分区間を保持し、対数時間でプレフィックス和と点更新に答えます。各ナビゲートはひとつのビット技法に依存します。現在の1始まりインデックスの最下位セットビットで、二の補数では lsb は i と -i のビット積です。その lsb を足すと更新連鎖を辿り、引くとプレフィックス照会連鎖を辿ります。学生・競技プログラマー・ライブラリ作者は、試験の圧力下で恒等式を再導出せずに親・次インデックスが必要です。本ツールは正のインデックス i と任意の木サイズ n を受け取り、lsb、1ステップの更新先と照会親、学習用の二進表現、n 指定時は古典的BITコードと同じ更新経路と照会経路を返します。

Fenwickインデックスが最下位セットビットを使う理由

1始まりの binary indexed tree では、インデックス i のセルは、長さが i の最下位セットビットに等しい、下層配列の連続区間を担当します。その長さは lsb を i と二の補数での -i のビット積として求めます。固定幅整数のモジュラ演算を使う言語では i and minus i と書くことが多いです。

幾何的には、最下位の1ビットより下の全ビットを反転するとその2の累乗が分離され、元のインデックスとのビット積でちょうどその累乗が得られます。古典的な更新ループは変更したインデックスから始まり、i が木サイズ n 以内のあいだ i を i プラス lsb に置き換え、各ステップでデルタを吸収すべき次のインデックスへジャンプします。

古典的なプレフィックス照会ループはプレフィックス右端から始まり、i が正のあいだ i を i マイナス lsb に置き換え、1から元のインデックスまでを敷き詰める担当セルを加算します。この2つの走査を合わせると、2つのプレフィックスの包含で区間和を実現します。

1ステップだけ—更新先は i プラス lsb、照会親は i マイナス lsb—を理解すれば、off-by-one のデバッグ、ホワイトボードでの責任木の図示、教科書の恒等式との一致確認ができます。コンテスト用テンプレートや本番の分析パイプラインへ組み込む前に、実装を検証してください。

Fenwick木の移動計算が役立つ場面

競技プログラミングの指導者やオンラインジャッジは、学習者が手書きで更新・照会ループを書くあいだに親・次ステップを確認できるよう、Fenwick木インデックス計算を使います。面接対策ツールには、同じ整数入力で標準BIT教程と一致する決定的オラクルが必要で、2の累乗の1つ前のような扱いにくいインデックスも含みます。検証失敗は残高を消費しません。

インデックスを32ビット正の範囲に保ち、size 設定時はテストで経路配列を固定すれば、宿題・ドキュメントのスクリーンショット・エッジワーカー向けに再現可能なナビゲートが得られ、自前の完全なデータ構造サンドボックスは不要です。

活用例

面接・テンプレート検証

候補のBIT実装を、固定サイズでの更新およびプレフィックス照会インデックス列の決定的オラクルと比較します。

よくある質問

インデックスは0始まりですか、1始まりですか？

標準の Fenwick / binary indexed tree と同様に1始まりです。インデックスは 1 から 2147483647 までの整数でなければなりません。

最下位セットビットに i & -i を使う理由は？

二の補数では -i が i の最下位1ビットより下を反転し、ビット積がその2の累乗を分離します。それがセル i の担当長さそのものです。

サイズ16の木で添字13の経路はどうなりますか？

サイズ16では、更新の経路は13、14、16で、13の変更を反映するセルを順にたどります。和の経路は13、12、8で、13までの累積和に足し合わせるセルです。

Fenwick木は何に使いますか？

累積和の計算と1つの値の更新を、対数時間で行うための仕組みです。各セルは長さが2のべき乗の部分範囲を受け持つので、和も更新も少数のセルしか触りません。

どの添字を入力できますか？

1から2147483647までの整数です。これは32ビットで表せる最大の正の値です。木のサイズも指定する場合は、添字以上で、同じ上限以内にする必要があります。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/dev/fenwick-index

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/dev/fenwick-index \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"index":13}'

const res = await fetch("https://api.kit.forhosting.com/dev/fenwick-index", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "index": 13
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/fenwick-index",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "index": 13
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/fenwick-index", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"index":13}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"index":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/fenwick-index", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "index": 13
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.fenwick_index",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

純粋で決定的な論理により、無料ブラウザ利用と有料API呼び出しはバイト単位で一致します。

入力契約・応答フィールド・検証

index は1から2の31乗マイナス1までの閉区間にある正の整数で、JavaScript のビット演算が忠実な符号付き32ビット正の最大値までです。別名 i、idx、position も受け付けます。例：インデックス13の二進は zero-b one one zero one、最下位セットビット1、更新先14、照会親12；size 16では更新経路は13→14→16、照会経路は13→12→8です。図が必要ならご自身の配列可視化と組み合わせてください。必須フィールド index を含む JSON を POST してください。任意フィールド size（別名 n、n_max、tree_size）は木の最大インデックスで、指定時は index 以上かつ同じ上限以下の整数でなければなりません。欠落・非整数・0・範囲外は invalid_input でフィールド名を示して失敗し、課金されません。成功時の本文には常に index、lowest_set_bit、update_next、query_parent、zero-b 接頭辞付きの binary と lsb_binary、恒等式を述べる短い formula が含まれます。size 指定時は size、更新ループが訪れる順序付きインデックス一覧 update_path、プレフィックスループの query_path、1ステップ更新先が木内に残るかの真偽値 update_next_in_range も含まれます。本エンドポイントはインデックス算術のみを計算し、木の値を保存したりユーザー配列への和照会を行ったりはしません。

FenwickインデックスAPIが役立つ場面

実装は pure parse のティアAのため、成功した各呼び出しはモデルトークンも外向きネットワークもなく公開の基本料金 $0.002 です。

連携の活用例

コンテスト・宿題向けBIT演習

学習者にインデックス i と任意の size n を与え、手書きのFenwickループと照合して lowest_set_bit、update_next、query_parent、完全経路を検証します。

ドキュメント・ライブラリ用ゴールデン経路

binary indexed tree の文書、単体テスト、言語間移植性チェック向けに update_path と query_path のフィクスチャを生成します。

技術的な質問

Fenwick木の親・次インデックスはどう計算しますか？

正の1始まりインデックス i を送ってください。API は lsb = i & -i、update_next = i + lsb、query_parent = i - lsb、および i と lsb の二進表現を返します。

任意パラメータ size は何をしますか？

size n が設定され n >= index のとき、応答に update_path（i <= n のあいだ i += lsb）と query_path（i > 0 のあいだ i -= lsb）が追加され、古典的BITループと一致します。

Fenwick木インデックス計算の料金は？

ブラウザツールは無料です。API リクエストは成功1回あたり $0.002 のKIT前払い残高を使い、無効入力は課金されません。

KITの完全なドキュメントを見る →