This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "data_structure/fenwick_tree.cpp"
#include "other/plus_monoid.cpp"
#include <iostream>
int main() {
#include "other/fast_ios.cpp"
using i64 = long long;
int n, q;
std::cin >> n >> q;
fenwick_tree<plus_monoid<i64>> ft(n);
for (int i = 0; i != n; i += 1) {
i64 a;
std::cin >> a;
ft.add(i, a);
}
for (int i = 0; i != q; i += 1) {
int t;
std::cin >> t;
switch (t) {
case 0: {
int p;
i64 x;
std::cin >> p >> x;
ft.add(p, x);
} break;
case 1: {
int l, r;
std::cin >> l >> r;
std::cout << -ft.fold_prefix(l) + ft.fold_prefix(r) << "\n";
} break;
}
}
}
#line 1 "test/fenwick_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 2 "other/int_alias.cpp"
#include <cstddef>
#include <cstdint>
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "data_structure/fenwick_tree.cpp"
#include <cassert>
#line 5 "data_structure/fenwick_tree.cpp"
#include <vector>
template <class M> class fenwick_tree {
using T = typename M::value_type;
public:
using value_type = T;
private:
std::vector<T> tree;
public:
fenwick_tree() = default;
explicit fenwick_tree(const usize size) : tree(size + 1, M::identity) {}
bool empty() const { return size() == 0; }
usize size() const { return tree.size() - 1; }
T fold_prefix(usize last) const {
assert(last <= size());
T ret = M::identity;
while (last != 0) {
ret = M::operation(tree[last], ret);
last &= last - 1;
}
return ret;
}
void add(usize index, const T value) {
assert(index < size());
index += 1;
while (index < tree.size()) {
tree[index] = M::operation(tree[index], value);
index += index & ~index + 1;
}
}
};
/**
* @brief Fenwick Tree
* @see https://scrapbox.io/data-structures/Fenwick_Tree
*/
#line 1 "other/plus_monoid.cpp"
template <class T> class plus_monoid {
public:
using value_type = T;
static T operation(const T l, const T r) { return l + r; }
static constexpr T identity = 0;
};
#line 5 "test/fenwick_tree.test.cpp"
#include <iostream>
int main() {
#line 1 "other/fast_ios.cpp"
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#line 10 "test/fenwick_tree.test.cpp"
using i64 = long long;
int n, q;
std::cin >> n >> q;
fenwick_tree<plus_monoid<i64>> ft(n);
for (int i = 0; i != n; i += 1) {
i64 a;
std::cin >> a;
ft.add(i, a);
}
for (int i = 0; i != q; i += 1) {
int t;
std::cin >> t;
switch (t) {
case 0: {
int p;
i64 x;
std::cin >> p >> x;
ft.add(p, x);
} break;
case 1: {
int l, r;
std::cin >> l >> r;
std::cout << -ft.fold_prefix(l) + ft.fold_prefix(r) << "\n";
} break;
}
}
}