# Binary-Indexed Tree

```template <typename T>
class BIT {
private:
static const int MAXN = N + 100;
T a[MAXN];

public:
void add(int x, T d) {
x++;
while (x < MAXN) {
a[x] += d;
x += x & -x;
}
}
T query(int x) {
x++; T ret = 0;
while (x) {
ret += a[x];
x -= x & -x;
}
return ret;
}
T query_interval(int a, int b) {
// closed interval
return query(b) - query(a - 1);
}
int lower_bound(T x) {
int ret = 0; T cnt = 0;
int MAX = int(ceil(log(MAXN) / log(2)));
for (int i = MAX; i >= 0; --i) {
ret += 1 << i;
if (ret > N || cnt + a[ret] >= x)
ret -= 1 << i;
else cnt += a[ret];
}
if (ret >= N) return INF;
return max(ret, 1);
}

/***** The following should be used exclusively *****/
inline T query2(int x) {
// used to query some value (not some sum)
return query(x);
}
void add2(int a, int b, T d) {
}
};
```
```namespace bit {
using T = LL;
const int M = -1;
T c[M];
inline int lowbit(int x) { return x & -x; }
void add(int p, T v) {
for (int i = p + 1; i < M; i += lowbit(i))
c[i] += v;
}
T sum(int p) {
T ret = 0;
for (int i = p + 1; i > 0; i -= lowbit(i))
ret += c[i];
return ret;
}
int kth(T k) {
int ret = 0;
T cnt = 0;
FORD (i, 20, -1) {
ret += 1 << i;
if (ret >= M || cnt + c[ret] >= k)
ret -= 1 << i;
else cnt += c[ret];
}
return ret + 1;
}
}
```