Fenwick tree (BIT)

১ · সমস্যা — বদলাতে থাকা খাতায় “এ পর্যন্ত মোট কত?”

ধরুন একজন bKash এজেন্ট দিনের প্রতিটি ঘণ্টার লেনদেন একটি খাতায় লেখেন: ঘর ১-এ প্রথম ঘণ্টার মোট টাকা, ঘর ২-এ দ্বিতীয় ঘণ্টার, এভাবে। সারাদিন দুই ধরনের ঘটনা আসে। কখনো খবর আসে “৩ নম্বর ঘণ্টার একটি লেনদেন ভুল লেখা হয়েছিল, ৫০০ টাকা বাড়াও” — একটি ঘরের মান বদলাল। আবার কখনো মালিক জানতে চান “শুরু থেকে ৭ নম্বর ঘণ্টা পর্যন্ত মোট কত টাকা?” — একটি prefix sum. প্রশ্ন আর বদল মিশে আসছে, আর দুটিই লাখে লাখে।

পর্ব ১৭-এ আমরা দুটি সরল উপায় দেখেছি, আর দুটিরই একটি দুর্বল দিক আছে।

n = q = 10⁶ হলে প্রথম দুই উপায়ে প্রায় 10¹² ধাপ — অচল। Fenwick tree-তে প্রায় 2 × 10⁷ ধাপ — এক সেকেন্ডের অনেক কম। পর্ব ৩৪-এর segment tree-ও একই কাজ O(log n)-এ করে। তবে Fenwick tree, যার আরেক নাম Binary Indexed Tree (BIT), অনেক ছোট: কোড প্রায় দশ লাইন, আর জায়গা ঠিক n + 1 টি সংখ্যা। এর পুরো রহস্য লুকিয়ে আছে সংখ্যার binary রূপে।

২ · মূল ধারণা — প্রতিটি ঘরে একটি ব্লক, দৈর্ঘ্য lowbit

অ্যারে a-কে 1-based ধরুন: a[1], a[2], …, a[n]. Fenwick tree হলো আরেকটি অ্যারে t[1..n]. প্রতিটি i-এর জন্য সংজ্ঞা একটি:

যেমন 6 = 110, সবচেয়ে নিচের 1-bit-এর মান 2, তাই t[6] = a[5] + a[6]. আবার 8 = 1000, lowbit 8, তাই t[8] = a[1] + … + a[8]. বিজোড় সংখ্যার lowbit সবসময় 1, তাই t[1], t[3], t[5], t[7] শুধু নিজের ঘর রাখে। নিচের ছবিতে n = 8-এর সব ব্লক:

pos     1  2  3  4  5  6  7  8     i (binary)  lowbit  block
t[1]    ███                        0001        1       a[1]
t[2]    ██████                     0010        2       a[1..2]
t[3]          ███                  0011        1       a[3]
t[4]    ████████████               0100        4       a[1..4]
t[5]                ███            0101        1       a[5]
t[6]                ██████         0110        2       a[5..6]
t[7]                      ███      0111        1       a[7]
t[8]    ████████████████████████   1000        8       a[1..8]

এই পর্বের উদাহরণ-অ্যারে a = [5, 2, 9, 1, 6, 3, 4, 8] (ঘর 1 থেকে 8). সংজ্ঞা থেকে t = [5, 7, 9, 17, 6, 9, 4, 38]: যেমন t[4] = 5 + 2 + 9 + 1 = 17, t[6] = 6 + 3 = 9, আর t[8] = সবার যোগফল 38.

lowbit বের করা — i & −i আর 2's complement

সবচেয়ে নিচের 1-bit এক লাইনে পাওয়া যায়: i & -i. এখানে & হলো bitwise AND, আর −i কম্পিউটার রাখে 2's complement রূপে: সব bit উল্টে দিয়ে 1 যোগ (বিস্তারিত: কম্পিউটারের মৌলিক বিষয় · বাইনারি গণিত আর complement). কেন এটি কাজ করে, i = 12 নিয়ে দেখুন:

Python-এ int-এর আকারের কোনো সীমা নেই, তবু i & -i একই ফল দেয় — Python ঋণাত্মক সংখ্যার bitwise কাজ এমনভাবে করে যেন বাঁ দিকে অসীম 1 আছে, অর্থাৎ 2's complement-এর মতোই। C++-এ int বা long long-এ এটি নিরাপদ। unsigned ধরনেও -i একই bit দেয় (কিছু compiler সতর্কবার্তা দেখায়); চাইলে i & (~i + 1) লিখুন, বা C++20-এর <bit> header-এর std::countr_zero দিয়ে (1 << countr_zero(i)) পাওয়া যায়।

কেন 1-based?

পুরো কাঠামো দাঁড়িয়ে আছে “i-এর সবচেয়ে নিচের 1-bit”-এর ওপর। i = 0-এর কোনো 1-bit নেই — lowbit(0) = 0, তাই 0 থেকে নামলে বা উঠলে i বদলায় না, লুপ চিরকাল চলে। এজন্য Fenwick tree-তে index 1 থেকে n; অ্যারেটি n + 1 আকারের, আর t[0] অব্যবহৃত। 0-based ইনপুট এলে সবচেয়ে নিরাপদ নিয়ম: BIT-এর সীমানায় ঢোকার সময় +1 করুন (add(i + 1, v)), ভেতরে সবকিছু 1-based রাখুন। (0-based-এর একটি আলাদা রূপও আছে, ভাবনার প্রশ্ন ০৩ দেখুন।)

৩ · Prefix query — lowbit বাদ দিয়ে নিচে নামা

prefix(i) = a[1] + … + a[i] কীভাবে পাবেন? t[i] দেয় শেষের lowbit(i) টি ঘর, অর্থাৎ (i − lowbit(i), i]. বাকি থাকে [1, i − lowbit(i)] — আবার একটি prefix, এবার ছোট। তাই i থেকে lowbit বাদ দিয়ে একই কাজ চালিয়ে যান, যতক্ষণ i শূন্য না হয়।

Pseudocode — Fenwick tree (1-based, t[1..n])

prefix(i):   s = 0
             while i > 0:
                 s = s + t[i]
                 i = i - lowbit(i)          // drop the lowest 1-bit
             return s

add(i, v):   while i <= n:
                 t[i] = t[i] + v
                 i = i + lowbit(i)          // jump to the next block that contains i

a = [5, 2, 9, 1, 6, 3, 4, 8] আর t = [5, 7, 9, 17, 6, 9, 4, 38] নিয়ে prefix(7) দেখুন। নিচের “used” সারিতে লেখা আছে প্রতিটি ঘর কোন t-এর ব্লক থেকে যোগ হলো:

কেন ঠিক, আর কেন O(log n)

সঠিকতা. লুপের প্রতিটি পুনরাবৃত্তির শুরুতে এই invariant সত্য: s = a[i + 1] + … + a[i₀], যেখানে i₀ হলো শুরুর i. শুরুতে i = i₀, যোগফলটি ফাঁকা, s = 0 — সত্য। এক ধাপে s-এ t[i] যোগ হয়, যা ঠিক a[i − lowbit(i) + 1 … i], আর i হয় i − lowbit(i) — তাই invariant আবার সত্য। লুপ শেষে i = 0, অর্থাৎ s = a[1] + … + a[i₀]. ব্লকগুলো কখনো একে অন্যের ওপর পড়ে না, কারণ প্রতিটি নতুন ব্লক ঠিক আগেরটির বাঁ পাশে শেষ হয়।

সময়. i − lowbit(i) মানে i-এর সবচেয়ে নিচের 1-bit মুছে ফেলা। প্রতি ধাপে একটি 1-bit কমে, তাই ধাপের সংখ্যা = i-এর binary রূপে 1-এর সংখ্যা, যাকে বলে popcount. i ≤ n হলে i-এ সর্বোচ্চ ⌊log₂ n⌋ + 1 টি bit, তাই prefix সর্বোচ্চ ⌊log₂ n⌋ + 1 ধাপ: O(log n) সময়, আর বাড়তি জায়গা O(1). সবচেয়ে খারাপ i হলো 2^k − 1 ধাঁচের (যেমন 7 = 111, 15 = 1111), সবচেয়ে ভালো 2-এর ঘাত (একটিই ধাপ)।

৪ · Point update — lowbit যোগ করে ওপরে ওঠা

এবার উল্টো প্রশ্ন: a[p]-এ v যোগ হলে কোন কোন t বদলাবে? ঠিক সেগুলো, যাদের ব্লকে p আছে। সংখ্যায় তারা কম — আর তাদের খুঁজে পাওয়ার নিয়মটিও lowbit: p থেকে শুরু করে বারবার i += lowbit(i), যতক্ষণ i ≤ n. প্রথমে দেখুন, তারপর প্রমাণ।

প্রমাণ — ওপরে ওঠার পথ ঠিক সেই ব্লকগুলো ছোঁয়, যাদের মধ্যে p আছে

ব্লক j-কে লিখি B(j) = (j − lowbit(j), j]. দুটি ছোট পর্যবেক্ষণ লাগবে। ধরুন L = lowbit(j).

• (ক) পরের ব্লক আগেরটিকে ধারণ করে। j + L-এ carry চলে, তাই lowbit(j + L) ≥ 2L. ফলে B(j + L)-এর শুরু ≤ (j + L) − 2L = j − L, আর শেষ j + L — অর্থাৎ B(j) ⊂ B(j + L).
• (খ) মাঝের কেউ ধারণ করে না। j < j′ < j + L হলে j′ = j + r, যেখানে 0 < r < L. j-এর নিচের সব bit 0, তাই lowbit(j′) = lowbit(r), আর B(j′) শুরু হয় j + r − lowbit(r) ≥ j থেকে। অর্থাৎ B(j′)-এ j বা তার আগের কোনো ঘর নেই।

এখন p দিয়ে শুরু করুন। B(p)-এ p আছে, আর p-এর চেয়ে ছোট কোনো j-এর ব্লকে p থাকতে পারে না (ব্লক j-তে শেষ হয়)। (খ) বলে p আর p + lowbit(p)-এর মাঝের কোনো ব্লকে p নেই, (ক) বলে পরেরটিতে আছে। Induction চালালে: ওপরে ওঠার পথ p ধারণকারী সব ব্লক ছোঁয়, আর অন্য কাউকে ছোঁয় না। তাই একটি add-এর পর প্রতিটি t[j] তার সংজ্ঞা মেনে চলে।

সময়. (ক)-এর যুক্তি থেকে প্রতি ধাপে lowbit অন্তত দ্বিগুণ হয় — সবচেয়ে নিচের 1-bit-এর অবস্থান অন্তত এক ঘর ওপরে যায়। অবস্থান ০ থেকে শুরু করে ⌊log₂ n⌋ ছাড়ালে i > n, তাই add সর্বোচ্চ ⌊log₂ n⌋ + 1 ধাপ: O(log n) সময়, O(1) বাড়তি জায়গা। মজার একটি প্রতিসাম্য: query 1-bit মোছে, update 1-bit-কে ওপরে ঠেলে।

৫ · O(n) build আর রেঞ্জের যোগফল

শুরুর অ্যারে থেকে t বানানোর সরল উপায়: t সব শূন্য, তারপর প্রতিটি i-এ add(i, a[i]) — n টি add, মোট O(n log n). কিন্তু O(n)-এ সম্ভব। লক্ষ করুন, update-এর tree-তে i-এর parent হলো i + lowbit(i), আর t[parent]-এর ব্লক তার সন্তানদের ব্লক আর নিজের ঘর মিলে তৈরি। তাই প্রথমে t = a কপি করুন, তারপর i = 1 থেকে n পর্যন্ত একবার হেঁটে প্রতিটি t[i]-কে শুধু তার parent-এ যোগ করুন:

কেন কাজ করে: i-এর সব সন্তান i-এর চেয়ে ছোট, তাই i-তে পৌঁছানোর আগেই তারা নিজেদের যোগফল t[i]-এ ঠেলে দিয়েছে — i-তে পৌঁছালে t[i] সম্পূর্ণ। আরেকটি O(n) উপায়: আগে prefix sum P বানিয়ে t[i] = P[i] − P[i − lowbit(i)].

যেকোনো রেঞ্জের যোগফল

a[l] + … + a[r] = prefix(r) − prefix(l − 1) — পর্ব ১৭-এর সেই পুরোনো কৌশল, শুধু এবার প্রতিটি prefix O(log n). যেমন sum(3..6) = prefix(6) − prefix(2) = (t[6] + t[4]) − t[2] = (9 + 17) − 7 = 19 = 9 + 1 + 6 + 3. সাবধান: l = 1 হলে prefix(0) = 0, লুপ একবারও চলে না — ঠিক যা চাই। এই বিয়োগটিই Fenwick tree-র শক্তি আর সীমা দুটোই, অংশ ৯-এ ফিরব।

পুরো কোড — BIT, আর brute force-এর সাথে মিলিয়ে দেখা

প্রথমে উপরের উদাহরণটি চালানো হয়, তারপর একটি stress test: ৫০ ঘরের একটি সাধারণ অ্যারে আর একটি BIT-এ একই ২০০০টি এলোমেলো আপডেট, প্রতিটির পর একটি এলোমেলো রেঞ্জে দুজনের উত্তর মেলানো (brute force সরাসরি যোগ করে)। এলোমেলো সংখ্যা আসে নিজের লেখা একটি ছোট সূত্র থেকে, যাতে C++ আর Python ঠিক একই ক্রম পায়।

#include <iostream>
#include <vector>
using namespace std;
struct BIT {                                        // 1-based: t[0] is unused
    int n; vector<long long> t;
    BIT(const vector<long long>& a) : n(int(a.size())), t(a.size() + 1, 0) {   // O(n) build
        for (int i = 1; i <= n; ++i) {
            t[i] += a[i - 1];
            if (int j = i + (i & -i); j <= n) t[j] += t[i];     // push into the parent
        }
    }
    void add(int i, long long v) { for (; i <= n; i += i & -i) t[i] += v; }   // walk UP
    long long prefix(int i) const { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }  // walk DOWN
    long long range_sum(int l, int r) const { return prefix(r) - prefix(l - 1); }
};
unsigned long long seed = 12345;
int rnd(int m) { seed = (seed * 1103515245 + 12345) % 2147483648ULL; return int(seed % m); }
void show(const BIT& b) { for (int i = 1; i <= b.n; ++i) cout << ' ' << b.t[i]; }
int main() {
    BIT b({5, 2, 9, 1, 6, 3, 4, 8});
    cout << "tree :"; show(b);
    cout << "\nprefix(7) = " << b.prefix(7) << " | sum(3..6) = " << b.range_sum(3, 6) << '\n';
    b.add(3, 5);
    cout << "after add(3, +5) tree :"; show(b); cout << " | prefix(7) = " << b.prefix(7) << '\n';
    const int n = 50; int bad = 0;                              // stress test against a plain array
    vector<long long> arr(n + 1, 0); BIT f(vector<long long>(n, 0));
    for (int it = 0; it < 2000; ++it) {
        int i = rnd(n) + 1, v = rnd(21) - 10;
        arr[i] += v; f.add(i, v);
        int l = rnd(n) + 1, r = l + rnd(n - l + 1);
        long long s = 0; for (int k = l; k <= r; ++k) s += arr[k];
        bad += f.range_sum(l, r) != s;
    }
    cout << "stress: 2000 random add+query pairs on n = 50, mismatches = " << bad << '\n';
}

tree : 5 7 9 17 6 9 4 38
prefix(7) = 30 | sum(3..6) = 19
after add(3, +5) tree : 5 7 14 22 6 9 4 43 | prefix(7) = 35
stress: 2000 random add+query pairs on n = 50, mismatches = 0

class BIT:                                # 1-based: t[0] is unused
    def __init__(self, a):                # O(n) build: each i pushes into one parent
        self.n, self.t = len(a), [0] + list(a)
        for i in range(1, self.n + 1):
            j = i + (i & -i)
            if j <= self.n:
                self.t[j] += self.t[i]
    def add(self, i, v):                  # point update: walk UP, adding lowbit
        while i <= self.n:
            self.t[i] += v; i += i & -i
    def prefix(self, i):                  # a[1] + ... + a[i]: walk DOWN, removing lowbit
        s = 0
        while i > 0:
            s += self.t[i]; i -= i & -i
        return s
    def range_sum(self, l, r): return self.prefix(r) - self.prefix(l - 1)

b = BIT([5, 2, 9, 1, 6, 3, 4, 8])
print("tree :", *b.t[1:])
print("prefix(7) =", b.prefix(7), "| sum(3..6) =", b.range_sum(3, 6))
b.add(3, 5)
print("after add(3, +5) tree :", *b.t[1:], "| prefix(7) =", b.prefix(7))
seed, n, bad = 12345, 50, 0               # stress test against a plain list
def rnd(m):
    global seed
    seed = (seed * 1103515245 + 12345) % 2147483648
    return seed % m
arr, f = [0] * (n + 1), BIT([0] * n)
for _ in range(2000):
    i, v = rnd(n) + 1, rnd(21) - 10
    arr[i] += v; f.add(i, v)
    l = rnd(n) + 1; r = l + rnd(n - l + 1)
    bad += f.range_sum(l, r) != sum(arr[l:r + 1])
print("stress: 2000 random add+query pairs on n = 50, mismatches =", bad)

tree : 5 7 9 17 6 9 4 38
prefix(7) = 30 | sum(3..6) = 19
after add(3, +5) tree : 5 7 14 22 6 9 4 43 | prefix(7) = 35
stress: 2000 random add+query pairs on n = 50, mismatches = 0

৬ · রেঞ্জ আপডেট — difference array-এর ওপর BIT, আর দুই BIT-এর কৌশল

Range update + point query

এবার উল্টো চাহিদা: “a[l..r]-এর প্রতিটি ঘরে v যোগ করো” (range update), আর প্রশ্ন “এখন a[i] কত?”. পর্ব ১৭-এর difference array মনে করুন: d[i] = a[i] − a[i − 1], তাই a[i] = d[1] + … + d[i] — একটি prefix sum! আর a[l..r]-এ v যোগ মানে শুধু d[l] += v আর d[r + 1] −= v. তাই BIT রাখুন d-এর ওপর:

Pseudocode — range update, point query (1-based, BIT over d)

rangeAdd(l, r, v):  add(l, v);  add(r + 1, -v)      // skip the second if r + 1 > n
pointQuery(i):      return prefix(i)                 // a[i] = d[1] + ... + d[i]

দুটিই O(log n). উদাহরণ: n = 6, সব শূন্য; rangeAdd(2, 4, +3) মানে add(2, 3) আর add(5, −3). এখন pointQuery(3) = d[1] + d[2] + d[3] = 0 + 3 + 0 = 3, আর pointQuery(5) = 3 − 3 = 0 — ঠিক।

Range update + range query — দুই BIT, সূত্রটি নিজে বের করুন

যদি রেঞ্জে যোগও করতে হয় আর রেঞ্জের যোগফলও জানতে হয়? চাই S(x) = a[1] + … + a[x]. a[i]-এর জায়গায় d বসান:

হাতে যাচাই: n = 5, সব শূন্য, rangeAdd(2, 4, +3) → a = [0, 3, 3, 3, 0]. B1-এ ঘর 2-এ +3, ঘর 5-এ −3; B2-এ ঘর 2-এ +6, ঘর 5-এ −15. S(3) = 4 · 3 − 6 = 6 = 0 + 3 + 3. S(5) = 6 · (3 − 3) − (6 − 15) = 9 = 3 + 3 + 3. দুটি কাজই চারটি বা কম BIT-কাজ: O(log n) প্রতিটি, জায়গা 2(n + 1). এটি পর্ব ৩৫-এর lazy segment tree-র একটি হালকা বিকল্প — শুধু যোগের ক্ষেত্রে।

2D BIT — গ্রিডের আয়তক্ষেত্র

একটি n × m গ্রিডে কোনো ঘরের মান বদলায়, আর প্রশ্ন আসে “বাঁ-ওপরের কোণ থেকে (x, y) পর্যন্ত আয়তক্ষেত্রের যোগফল কত?”. সমাধান: BIT-এর ভেতরে BIT — 2D Fenwick tree. t[x][y] রাখে x-এর ব্লক × y-এর ব্লক, আর দুই লুপ একটির ভেতরে আরেকটি:

Pseudocode — 2D BIT (1-based, t[1..n][1..m])

add(x, y, v):  for (i = x; i <= n; i += lowbit(i))
                   for (j = y; j <= m; j += lowbit(j))  t[i][j] += v
prefix(x, y):  s = 0
               for (i = x; i > 0; i -= lowbit(i))
                   for (j = y; j > 0; j -= lowbit(j))   s += t[i][j]
               return s

প্রতিটি কাজ O(log n · log m), জায়গা Θ(nm). যেকোনো আয়তক্ষেত্র (x1, y1)–(x2, y2)-এর যোগফল আসে চারটি prefix থেকে inclusion–exclusion দিয়ে: P(x2, y2) − P(x1 − 1, y2) − P(x2, y1 − 1) + P(x1 − 1, y1 − 1) — পর্ব ১৭-এর 2D prefix sum-এর মতোই, কিন্তু এবার আপডেটসহ। গ্রিড খুব বড় হলে (যেমন 10⁹ × 10⁹) nm জায়গা অসম্ভব; তখন প্রশ্নগুলো আগে জেনে offline পদ্ধতিতে এক মাত্রার BIT আর সর্ট দিয়ে সমাধান করা হয়।

৭ · k-তম উপাদান — BIT-এর ওপর binary lifting

ধরুন একটি ভর্তি পরীক্ষার নম্বর 1 থেকে n-এর মধ্যে, আর BIT-এর ঘর v রাখে “কতজন v নম্বর পেয়েছে” — একটি frequency array. নতুন খাতা এলে add(v, +1), পুনর্নিরীক্ষায় নম্বর বদলালে add(পুরোনো, −1) আর add(নতুন, +1). এখন প্রশ্ন: “নম্বর অনুযায়ী সাজালে k-তম জন কত পেয়েছে?” — একটি order statistic, যেমন median.

সহজ উপায়: “prefix(v) ≥ k হয় এমন সবচেয়ে ছোট v” খুঁজতে prefix-এর ওপর binary search — log n টি prefix, প্রতিটি log n: O(log² n). কিন্তু BIT-এর গঠন কাজে লাগালে একবারের হাঁটাতেই O(log n) হয়। ধারণা: উত্তরের ঠিক আগের অবস্থান pos-কে bit ধরে ধরে ওপর থেকে বানান — binary lifting.

Pseudocode — k-th smallest (1-based, all counts >= 0, 1 <= k <= total)

kth(k):  pos = 0
         for step = (largest power of 2 <= n) down to 1, halving:
             if pos + step <= n and t[pos + step] < k:
                 pos = pos + step          // the answer lies further right
                 k = k - t[pos]            // skip everything in (old pos, pos]
         return pos + 1

চাবিকাঠি হলো: pos-এ এখন পর্যন্ত শুধু step-এর চেয়ে বড় 2-এর ঘাত যোগ হয়েছে, তাই lowbit(pos + step) = step — অর্থাৎ t[pos + step] ঠিক (pos, pos + step]-এর গণনা, আলাদা কোনো prefix লাগে না। একটি উদাহরণ: n = 8, গণনা c = [2, 0, 1, 3, 0, 1, 2, 1] (মোট ১০ জন), তাহলে t = [2, 2, 1, 6, 0, 1, 2, 10]. ৬ষ্ঠ জন কত পেয়েছে?

শর্ত দুটি মনে রাখুন: সব গণনা অ-ঋণাত্মক হতে হবে (তবেই prefix একমুখীভাবে বাড়ে আর “সবচেয়ে ছোট v” অর্থবহ), আর k ≤ মোট গণনা। মান বড় বা ছড়ানো হলে আগে coordinate compression — পরের অংশ। কনটেস্টে এই কৌশল দিয়ে “চলমান median” বা “k-তম ছোট মান, মাঝে মাঝে মোছাসহ” সমস্যা মাত্র কয়েক লাইনে হয়, balanced BST (পর্ব ২৮–২৯) ছাড়াই।

৮ · Inversion গোনা — BIT আর coordinate compression

একটি অ্যারের inversion হলো এমন জোড়া (i, j), যেখানে i < j কিন্তু a[i] > a[j]. পর্ব ২১-এ merge sort-এর merge ধাপে এগুলো গুনেছি, O(n log n)-এ। BIT দিয়ে আরেকটি সমান দ্রুত, আর অনেক সময় বেশি নমনীয় উপায় আছে: বাঁ থেকে ডানে হাঁটুন, আর প্রতিটি নতুন x-এর জন্য জিজ্ঞেস করুন “আগে দেখা মানগুলোর কয়টি x-এর চেয়ে বড়?”. আগে দেখা মানগুলোর একটি frequency BIT রাখলে উত্তর = (এ পর্যন্ত দেখা) − prefix(x), কারণ prefix(x) গোনে কয়টি ≤ x.

সমস্যা একটাই: মান 10⁹ পর্যন্ত হলে 10⁹ ঘরের BIT অসম্ভব। কিন্তু inversion শুধু মানগুলোর ক্রম দেখে, আকার নয়। তাই পর্ব ২৫-এর coordinate compression: মানগুলো সর্ট করে ডুপ্লিকেট বাদ দিন, আর প্রতিটি মানকে তার অবস্থান (rank) 1..k দিয়ে বদলান। ক্রম অক্ষত থাকে, BIT লাগে মাত্র k ≤ n ঘরের।

সময়: compression-এর সর্ট O(n log n), তারপর n টি prefix আর n টি add, প্রতিটি O(log k): মোট O(n log n), জায়গা O(n). উত্তর n(n − 1)/2 পর্যন্ত হতে পারে — n = 2 × 10⁵-এ প্রায় 2 × 10¹⁰, তাই C++-এ long long বাধ্যতামূলক।

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
long long inversions_bit(const vector<long long>& a) {         // O(n log n)
    vector<long long> vals(a); sort(vals.begin(), vals.end());   // coordinate compression
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int k = int(vals.size()); vector<int> t(k + 1, 0); long long inv = 0;
    for (int seen = 0; seen < int(a.size()); ++seen) {
        int r = int(lower_bound(vals.begin(), vals.end(), a[seen]) - vals.begin()) + 1;   // rank 1..k
        int s = 0;
        for (int j = r; j > 0; j -= j & -j) s += t[j];           // s = how many seen values are <= x
        inv += seen - s;                                         // seen values strictly greater than x
        for (; r <= k; r += r & -r) t[r] += 1;
    }
    return inv;
}
long long inversions_brute(const vector<long long>& a) {      // O(n^2) reference
    long long c = 0;
    for (size_t i = 0; i < a.size(); ++i) for (size_t j = i + 1; j < a.size(); ++j) c += a[i] > a[j];
    return c;
}
unsigned long long seed = 2026;
int rnd(int m) { seed = (seed * 1103515245 + 12345) % 2147483648ULL; return int(seed % m); }
int main() {
    vector<long long> a = {40, 10, 30, 10, 50, 20};
    cout << "a ="; for (auto x : a) cout << ' ' << x;
    cout << " -> BIT: " << inversions_bit(a) << " | brute: " << inversions_brute(a) << '\n';
    int bad = 0;
    for (int it = 0; it < 300; ++it) {
        vector<long long> b(rnd(40) + 1);
        for (auto& x : b) x = rnd(21) * 1000003LL;              // big values, many repeats
        bad += inversions_bit(b) != inversions_brute(b);
    }
    cout << "stress: 300 random arrays, mismatches = " << bad << '\n';
    vector<long long> rev(2000); for (int i = 0; i < 2000; ++i) rev[i] = 2000 - i;
    cout << "reversed 1..2000: " << inversions_bit(rev) << " | expected " << 2000LL * 1999 / 2 << '\n';
}

a = 40 10 30 10 50 20 -> BIT: 7 | brute: 7
stress: 300 random arrays, mismatches = 0
reversed 1..2000: 1999000 | expected 1999000

def inversions_bit(a):                    # O(n log n)
    vals = sorted(set(a))                 # coordinate compression
    rank = {v: i + 1 for i, v in enumerate(vals)}   # ranks 1..k
    k = len(vals)
    t = [0] * (k + 1)
    inv = 0
    for seen, x in enumerate(a):          # seen = elements already inserted
        r, s = rank[x], 0
        j = r
        while j > 0:                      # s = how many seen values are <= x
            s += t[j]; j -= j & -j
        inv += seen - s                   # seen values strictly greater than x
        while r <= k:
            t[r] += 1; r += r & -r
    return inv

def inversions_brute(a):                  # O(n^2) reference
    return sum(a[i] > a[j] for i in range(len(a)) for j in range(i + 1, len(a)))

a = [40, 10, 30, 10, 50, 20]
print("a =", *a, "-> BIT:", inversions_bit(a), "| brute:", inversions_brute(a))
seed, bad = 2026, 0
def rnd(m):
    global seed
    seed = (seed * 1103515245 + 12345) % 2147483648
    return seed % m
for _ in range(300):
    b = [rnd(21) * 1000003 for _ in range(rnd(40) + 1)]   # big values, many repeats
    if inversions_bit(b) != inversions_brute(b): bad += 1
print("stress: 300 random arrays, mismatches =", bad)
print("reversed 1..2000:", inversions_bit(list(range(2000, 0, -1))), "| expected", 2000 * 1999 // 2)

a = 40 10 30 10 50 20 -> BIT: 7 | brute: 7
stress: 300 random arrays, mismatches = 0
reversed 1..2000: 1999000 | expected 1999000

৯ · BIT বনাম segment tree — আর একটু ইতিহাস

কেন min/max নয়? Fenwick tree রেঞ্জ [l, r]-এর উত্তর পায় prefix(r) থেকে prefix(l − 1) “বাদ দিয়ে”. যোগে বাদ দেওয়া মানে বিয়োগ; XOR-এ আবার XOR (x ^ x = 0); গুণে (শূন্য না থাকলে) ভাগ। এমন কাজকে বলা যায় উল্টানো যায় এমন (invertible). কিন্তু min(1..r) = 2 আর min(1..l − 1) = 2 জানলে min(l..r) কত — বলার উপায় নেই। তাই রেঞ্জের min/max-এর জন্য segment tree বা পর্ব ৩৭-এর sparse table. ব্যতিক্রম: শুধু prefix-এর max, আর মান শুধু বাড়ে — তখন BIT চলে (আরও গভীরে দেখুন)।

নিয়মটি সহজ: সমস্যা যদি “যোগফল বা গণনা, সাথে point update” — Fenwick tree, কারণ কম কোড মানে কম bug, আর কম জায়গা মানে cache-এ ভালো। রেঞ্জে min/max, “রেঞ্জে মান বসিয়ে দাও”, বা একাধিক তথ্য একসাথে লাগলে — segment tree.

১০ · AI-এর যুগে Fenwick tree — দশ লাইন, তিন জায়গায় off-by-one

“Fenwick tree লিখে দাও” বললে AI সহকারী সাধারণত ঠিকঠাক দেখতে দশ লাইন দেয়। ঝুঁকি লুকিয়ে থাকে সীমানায়: 0-based অ্যারেতে সরাসরি i & -i (i = 0-তে অসীম লুপ), i < n বনাম i <= n, prefix(l) বনাম prefix(l − 1). এগুলো off-by-one ভুল, যা ছোট উদাহরণে প্রায়ই ধরা পড়ে না। আর complexity-র প্রশ্নে AI কখনো বলে “build সবসময় O(n log n)”, বা ভুল করে রেঞ্জ minimum-এর জন্য BIT সুপারিশ করে।

BIT-এর কোডে AI সাধারণত যেসব ভুল করে

BIT-এর কোড যাচাইয়ের চেকলিস্ট

• সব index 1..n, অ্যারের আকার n + 1; 0-based ইনপুট BIT-এ ঢোকার সময়ই +1 করেছি
• query নিচে নামে (i -= i & -i, i > 0), update ওপরে ওঠে (i += i & -i, i ≤ n) — দিক দুটি হাতে একবার trace করেছি
• রেঞ্জ = prefix(r) − prefix(l − 1); edge case: l = 1, l = r, r = n, n = 1, ঋণাত্মক মান
• একটি সরল অ্যারে আর brute force-এর সাথে হাজারো এলোমেলো কাজে উত্তর মিলিয়েছি (stress testing), বিশেষ করে অনেক সমান মানসহ
• যোগফল আর inversion-এর উত্তর long long-এ; সবচেয়ে বড় সম্ভাব্য উত্তর হিসাব করে দেখেছি
• যে কাজটি রাখছি তা উল্টানো যায় কি না (যোগ, XOR) ভেবেছি — min/max হলে segment tree-র কথা ভেবেছি