BIT による転倒数
順序が逆転したペアを効率よく数えます
「BIT による転倒数」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
転倒とは
転倒とは、a[i] > a[j] となる i < j の組です。これは順序が逆になっている1組であり、その個数によって配列がどの程度整列されていないかを測れます。
転倒数が重要な理由
転倒数は、バブルソートが行う交換回数と等しくなります。競技プログラミングの問題では、順位付けや乱れに関する問題の中に登場します。
素朴な数え上げは遅すぎる
すべての組を調べると計算量は O(n^2) です。n が約 100000 の場合、チェック回数は100億回にもなり、時間制限を大幅に超えてしまいます。もっと賢い方法が必要です。🐢
BIT の考え方
左から右へ走査し、「現在の要素より大きい要素が、それより前にいくつあるか」と問いかけます。Fenwick tree なら、この問いに走査しながら答えられます。
出現頻度で数える
BIT は値ごとの頻度表を保持します。update(v, 1) によって、値 v がここまでの走査で出現したことを記録します。
update(v, 1)「大きい」は後ろの区間
v より大きい既出の値の個数は、既出の個数から v 以下の個数を引いたものです。i 番目の要素では、これはi minus query(v)になります。
inv += i - query(v)座標圧縮
値が大きかったり負数だったりする場合は、まずそれらを 1..n の順位に写像します。この圧縮により、順序を変えずに BIT を小さく保てます。
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}全体を走査する
配列をループし、各要素について大きい値の個数を合計に加えてから、現在の値を登録します。途中の合計が転倒数になります。
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)n log n で実行できる
各要素に対してクエリと更新を1回ずつ行い、どちらも O(log n) です。そのため、全体のカウントはO(n log n)時間で完了します。🚀
マージソートという親戚
マージソートも、マージの段階で O(n log n) の計算量で転倒数を数えられます。BIT を使う方法は、時間に追われているときでも実装が短くなりがちです。
カウントのオーバーフローに注意
転倒数は n の二乗の約半分に達することがあり、非常に大きくなります。Python の整数には上限がありませんが、ほかの言語では64ビット型が必要になります。
確認問題
走査の計算量を理解できているか確認しましょう。
振り返り：乱れを数える
左から右へ走査し、前に出現した大きい値の個数を BIT に尋ねることで、転倒数を O(n log n) で数えました。必要に応じて値を圧縮します。✅
よくある質問
「BIT による転倒数」レッスンは無料ですか？
はい。「BIT による転倒数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「BIT による転倒数」で何を学びますか？
順序が逆転したペアを効率よく数えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「BIT による転倒数」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。