コンテンツにスキップ

BIT

タグ「BIT」の記事 2 件

BIT のリンク集

BIT(Binary Indexed Tree、Fenwick Tree)について、参考になる記事や資料をまとめました。

BIT は、列に対して「1 点への加算」と「先頭からの和(prefix 和)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。区間 [l,r)[l, r) の和は、2 つの prefix 和の差で求まります。セグメント木よりできることは少ないものの、実装が短く高速です。BIT を 2 本使った区間加算や、BIT 上の二分探索(累積和が ww 以上になる最初の位置を O(log⁡N)O(\log N) で求める)もよく使われます。

  • Binary Indexed Tree のはなし(hos、JOI 春合宿 2014 の講義スライド)
    • BIT の動きを図で 1 ステップずつ追いながら、1 点加算・prefix 和、区間加算、2 次元 BIT、BIT 上の二分探索まで解説しています。日本語の BIT 解説の定番です。
    • p.75 の二分探索の擬似コードの「n 以下の最小の 2 ベキ」は「最大」の誤りです。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • 1 点加算・区間和から、BIT 2 本による区間加算、BIT 上の二分探索、転倒数、2 次元 BIT までを図と C++ のコードでまとめています。練習問題も付いています。
    • 転倒数の手順は、値が 1 以上であることを前提にしています。値に 0 があるときは、1 を足すか座標圧縮してから使ってください。
  • fenwick_tree のドキュメント
    • 公式の仕様です。0-indexed で、区間和は半開区間 [l,r)[l, r) で求めます。BIT 上の二分探索はありません。

BIT を扱う講座はまだありません。

  • Binary Indexed Tree(Fenwick Tree)(ikatakos)
    • Python の実装集です。区間加算(BIT 2 本)、累積和の二分探索、BIT に載せられる演算の条件、座標圧縮や辞書を使った BIT、2 次元 BIT まで扱っています。
    • 区間加算版の sum に : の抜けがあり、演算を渡せる版の lower_bound はそのままでは動きません。通常版の Bit.lower_bound は正しく動きます。
  • Binary Indexed Tree(Luzhiled’s Library)
    • BIT 上の二分探索 lower_bound・upper_bound を備えた実装です。1 点加算は apply、区間和は prod という名前です。
  • Fenwick Tree(data-structures)
    • BIT でできる操作を、可換モノイドの場合とアーベル群の場合に分けて整理しています。参考資料や実装へのリンクもまとまっています。
  • Fenwick tree(英語版 Wikipedia)
    • 同じ配列を、部分和用・更新用・二分探索用の 3 つの木として見ることで、BIT の構造を説明しています。
  • フェニック木(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、細かい誤りがあります。たとえば多次元の場合の計算量が O(4dlog⁡dn)O(4^d \log_d n) になっていますが、引用元では O(4dlog⁡dn)O(4^d \log^d n) です。
  • Fenwick Tree(cp-algorithms)
    • 0-indexed と 1-indexed の両方の実装、2 次元 BIT、BIT 2 本による区間加算・区間和まで扱っています。練習問題も多く載っています。

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。