# library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kazunetakahashi/library

# DataStructure/BIT.cpp

## Code

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

// ----- BIT -----
// referring to http://hos.ac/slides/20140319_bit.pdf

template <typename T>
class BIT
{
int N;
vector<T> data;

public:
BIT() {}
BIT(int N) : N{N}, data(N + 1) {}

void add(int i, T w) // data[i] += w;
{
for (; i < N; i |= i + 1)
{
data[i] += w;
}
}

void update(int i, T w) // data[i] = w;
{
}

T sum(int l, int r) // data[l] + \dots + data[r - 1]
{
return sum(r) - sum(l);
}

T operator[](int i) // data[i]
{
return sum(i, i + 1);
}

private:
T sum(int i) // data[0] + \dots + data[i - 1]
{
T res{0};
for (--i; i >= 0; i = (i & (i + 1)) - 1)
{
res += data[i];
}
return res;
}
};



#line 1 "DataStructure/BIT.cpp"
#include <iostream>
#include <vector>
using namespace std;

// ----- BIT -----
// referring to http://hos.ac/slides/20140319_bit.pdf

template <typename T>
class BIT
{
int N;
vector<T> data;

public:
BIT() {}
BIT(int N) : N{N}, data(N + 1) {}

void add(int i, T w) // data[i] += w;
{
for (; i < N; i |= i + 1)
{
data[i] += w;
}
}

void update(int i, T w) // data[i] = w;
{
}

T sum(int l, int r) // data[l] + \dots + data[r - 1]
{
return sum(r) - sum(l);
}

T operator[](int i) // data[i]
{
return sum(i, i + 1);
}

private:
T sum(int i) // data[0] + \dots + data[i - 1]
{
T res{0};
for (--i; i >= 0; i = (i & (i + 1)) - 1)
{
res += data[i];
}
return res;
}
};