// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
#include "src/datastructure/fenwick_tree.hpp"
#include <iostream>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
FenwickTree<int> ft(n);
while (q--) {
int com, x, y;
cin >> com >> x >> y;
if (com) cout << ft.find(x - 1, y) << endl;
else ft.add(x - 1, y);
}
return 0;
}
#line 1 "test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
#line 1 "src/datastructure/fenwick_tree.hpp"
#include <vector>
template<class T>
class FenwickTree {
private:
int n;
std::vector<T> tree;
public:
FenwickTree(int n) : n(n), tree(n) {}
void add(int i, T x) {
++i;
while (i <= n) {
tree[i - 1] += x;
i += i & -i;
}
}
T sum(int i) { // [0, i)
T s{0};
while (i > 0) {
s += tree[i - 1];
i -= i & -i;
}
return s;
}
T find(int l, int r) { // [l, r)
return sum(r) - sum(l);
}
};
#line 4 "test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp"
#include <iostream>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
FenwickTree<int> ft(n);
while (q--) {
int com, x, y;
cin >> com >> x >> y;
if (com) cout << ft.find(x - 1, y) << endl;
else ft.add(x - 1, y);
}
return 0;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_small_00.in |
![]() |
220 ms | 14 MB |
g++ | 00_small_01.in |
![]() |
13 ms | 14 MB |
g++ | 00_small_02.in |
![]() |
12 ms | 14 MB |
g++ | 00_small_03.in |
![]() |
12 ms | 14 MB |
g++ | 01_rand_00.in |
![]() |
12 ms | 14 MB |
g++ | 01_rand_01.in |
![]() |
12 ms | 14 MB |
g++ | 01_rand_02.in |
![]() |
12 ms | 14 MB |
g++ | 01_rand_03.in |
![]() |
13 ms | 14 MB |
g++ | 02_slight_00.in |
![]() |
12 ms | 14 MB |
g++ | 02_slight_01.in |
![]() |
13 ms | 14 MB |
g++ | 02_slight_02.in |
![]() |
16 ms | 14 MB |
g++ | 02_slight_03.in |
![]() |
43 ms | 14 MB |
g++ | 03_biased_00.in |
![]() |
13 ms | 14 MB |
g++ | 03_biased_01.in |
![]() |
92 ms | 14 MB |
g++ | 03_biased_02.in |
![]() |
106 ms | 14 MB |
g++ | 03_biased_03.in |
![]() |
114 ms | 14 MB |
g++ | 04_maximum_00.in |
![]() |
137 ms | 15 MB |
g++ | 04_maximum_01.in |
![]() |
126 ms | 14 MB |
g++ | 04_maximum_02.in |
![]() |
170 ms | 15 MB |
g++ | 04_maximum_03.in |
![]() |
159 ms | 15 MB |
clang++ | 00_small_00.in |
![]() |
11 ms | 12 MB |
clang++ | 00_small_01.in |
![]() |
11 ms | 16 MB |
clang++ | 00_small_02.in |
![]() |
11 ms | 16 MB |
clang++ | 00_small_03.in |
![]() |
12 ms | 14 MB |
clang++ | 01_rand_00.in |
![]() |
12 ms | 12 MB |
clang++ | 01_rand_01.in |
![]() |
12 ms | 14 MB |
clang++ | 01_rand_02.in |
![]() |
11 ms | 12 MB |
clang++ | 01_rand_03.in |
![]() |
12 ms | 14 MB |
clang++ | 02_slight_00.in |
![]() |
12 ms | 16 MB |
clang++ | 02_slight_01.in |
![]() |
13 ms | 16 MB |
clang++ | 02_slight_02.in |
![]() |
16 ms | 16 MB |
clang++ | 02_slight_03.in |
![]() |
45 ms | 16 MB |
clang++ | 03_biased_00.in |
![]() |
13 ms | 12 MB |
clang++ | 03_biased_01.in |
![]() |
113 ms | 12 MB |
clang++ | 03_biased_02.in |
![]() |
121 ms | 14 MB |
clang++ | 03_biased_03.in |
![]() |
118 ms | 14 MB |
clang++ | 04_maximum_00.in |
![]() |
137 ms | 14 MB |
clang++ | 04_maximum_01.in |
![]() |
129 ms | 14 MB |
clang++ | 04_maximum_02.in |
![]() |
125 ms | 14 MB |
clang++ | 04_maximum_03.in |
![]() |
141 ms | 16 MB |