This documentation is automatically generated by competitive-verifier/competitive-verifier
一点加算・区間和取得を対数時間で行うことができるデータ構造. セグメント木より定数倍が軽い.
BIT(n)
:要素数 n
の BIT を構築する.BIT(v)
:配列 v
の要素で BIT を構築する.sum(idx)
:$[1, \mathrm{idx}]$ の要素の総和を返す.sum(l, r)
:$[l, r]$ の要素の総和を返す.get(idx)
:$\mathrm{idx}$ 番目の要素の値を返す.add(idx, val)
:$\mathrm{idx}$ 番目の要素に val
を加える.idx
, l
, r
は 1-indexed である.
BIT(n)
:$O(n)$BIT(v)
:$O(n)$sum(idx)
:$O(\log n)$sum(l, r)
:$O(\log n)$get(idx)
:$O(\log n)$add(idx, val)
:$O(\log n)$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct BIT {
private:
vector<T> node;
const int N;
public:
BIT(int n) : node(n + 1, 0), N(n) {}
BIT(const vector<T> &v) : node(v.size() + 1, 0), N(v.size()) {
for(int i = 0; i < N; i++) node[i + 1] = v[i];
for(int i = 1; i < N; i++) {
int j = i + (i & -i);
if(j <= N) node[j] += node[i];
}
}
T sum(int idx) {
assert(0 <= idx && idx <= N);
T res = 0;
while(idx) {
res += node[idx];
idx -= idx & -idx;
}
return res;
}
T sum(int l, int r) {
assert(0 <= l && r <= N);
if(l > r) return T(0);
return sum(r) - sum(max(l - 1, 0));
}
inline T get(int idx) {
assert(0 < idx and idx <= N);
return sum(idx, idx);
}
void add(int idx, T val) {
assert(0 < idx && idx <= N);
while(idx <= N) {
node[idx] += val;
idx += idx & -idx;
}
}
};
#line 2 "tree/binary_indexed_tree.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct BIT {
private:
vector<T> node;
const int N;
public:
BIT(int n) : node(n + 1, 0), N(n) {}
BIT(const vector<T> &v) : node(v.size() + 1, 0), N(v.size()) {
for(int i = 0; i < N; i++) node[i + 1] = v[i];
for(int i = 1; i < N; i++) {
int j = i + (i & -i);
if(j <= N) node[j] += node[i];
}
}
T sum(int idx) {
assert(0 <= idx && idx <= N);
T res = 0;
while(idx) {
res += node[idx];
idx -= idx & -idx;
}
return res;
}
T sum(int l, int r) {
assert(0 <= l && r <= N);
if(l > r) return T(0);
return sum(r) - sum(max(l - 1, 0));
}
inline T get(int idx) {
assert(0 < idx and idx <= N);
return sum(idx, idx);
}
void add(int idx, T val) {
assert(0 < idx && idx <= N);
while(idx <= N) {
node[idx] += val;
idx += idx & -idx;
}
}
};