bit.sum,bit.add のやっていることを出力して確認したいです。

Question

前提

下記のプログラムでわからない箇所があるので、挙げさせていただきます。
些細なことでも結構ですので、お答えいただけると幸いです。

問題文：[ここから参照お願いします。](AtCoder ABC 107 D - Median of Medians)

参考にさせていただいたプログラム：ここから参照お願いします。

疑問点（よくわからない箇所）

• プログラムの60行目、63行目などにある、bit.sum,bit.add の動作がよくわかりません。

文字に置き換えて出力しようとするとエラーになりました。

入力

3
10 30 20

出力

sum=1
geta=4
sum+geta=5
num=1
sum=2
geta=4
sum+geta=6
num=2
sum=3
geta=4
sum+geta=7
・
・
・
sum+geta=6
num=2
sum=3
geta=4
sum+geta=7
num=3
1073741824
×

該当のソースコード

#include <iostream>
#include <vector>
using namespace std;

template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    long long N; cin >> N;
    vector<int> a(N); for (int i = 0; i < N; ++i) cin >> a[i];
    int low = 0, high = 1<<30;
    const int geta = N+1;
    while (high - low > 1) {
        /*cout << "high=" << high << endl;
        cout << "low=" << low << endl;*/
        int mid = (low + high) / 2;
        //cout << "mid=" << mid << endl;
        long long num = 0;
        BIT<long long> bit(N*2+10);
        int sum = 0;
        //cout << "sum+geta=" << sum+geta << endl;
        bit.add(sum+geta, 1);
        for (int i = 0; i < N; ++i) {
            int val;
            if (a[i] <= mid) val = 1; else val = -1;
            sum += val;
            cout << "sum=" << sum << endl;
            cout << "geta=" << geta << endl;
            cout << "sum+geta=" << sum+geta << endl;
            num += bit.sum(1, sum+geta);
            cout << "num=" << num << endl;
            //a=bit.add(sum+geta, 1);
            //cout << "bit.add=" << a << endl;
        }
        if (num > (N+1)*N/2/2) high = mid;
        else low = mid;
    }
    cout << high << endl;
}

試したこと

• 変数をそれぞれ出力
• bit.sumとかの出力を試してみる→＊をつけてもエラー

Comments

[actorbug]

そもそも、このコードは何をするものなのでしょうか。競プロなら問題も載せてください。
あと、BIT(Binary Indexed Tree)については既にご存じですか。

[actorbug]

このコードの場合、BITを使う意味はありません。
ループの中で毎回作り直して、毎回同じ位置にbit.addしているので、
bit.sum(1, sum+geta) は ((sum > 0) ? 1 : 0) と書いたのとまったく同じ意味となります。

[actorbug]

参考のプログラムと比較すると、内側のfor文の末尾の「bit.add(sum+geta, 1);」がコメントアウトされているため、正しい結果となりません。
あと、bitの中身を確認したいのなら、「bit.print();」と書けばよいです。

[actorbug]

解説をまじめに読んでみましたが、BITの中身を表示しても、何をやっているか理解するのは難しそうです。
参考プログラムからリンクの貼ってある「BITで転倒数を求める」( https://qiita.com/wisteria0410ss/items/296e0daa9e967ca71ed6 )を参照するか、それでも理解できなければ、「転倒数」で検索して自分に合う解説を見つけるのがよさそうです。

[SmaSTATION]

丁寧なご回答ありがとうございます．参照してみます！