# library

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

View the Project on GitHub kazunetakahashi/library

# DataStructure/tests/BIT.test.cpp

## Code

#include "../BIT.cpp"

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=ja"

int main()
{
int N;
cin >> N;
BIT<long long> tree{N};
int Q;
cin >> Q;
for (auto q{0}; q < Q; ++q)
{
int t;
cin >> t;
if (t == 0)
{
int k, x;
cin >> k >> x;
--k;
}
else
{
int s, t;
cin >> s >> t;
--s;
--t;
cout << tree.sum(s, t + 1) << endl;
}
}
}



#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;
}
};
#line 2 "DataStructure/tests/BIT.test.cpp"

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=ja"

int main()
{
int N;
cin >> N;
BIT<long long> tree{N};
int Q;
cin >> Q;
for (auto q{0}; q < Q; ++q)
{
int t;
cin >> t;
if (t == 0)
{
int k, x;
cin >> k >> x;
--k;
}
else
{
int s, t;
cin >> s >> t;
--s;
--t;
cout << tree.sum(s, t + 1) << endl;
}
}
}