bit.sum,bit.add の役割は何でしょうか。

前提

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

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

• プログラムの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
×

該当のソースコード

C++

#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とかの出力を試してみる→＊をつけてもエラー