This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "head.hpp"
#include "data_structure/1D-fenwick.hpp"
#include "io/Scanner.hpp"
#include "io/Printer.hpp"
using i64 = long long;
constexpr int mmax = 5E5 + 10;
Scanner scanner;
Printer printer;
Fenwick<i64> fenwick(mmax);
int main()
{
i64 n, q;
scanner.scan(n, q);
for(int i = 1;i <= n;i++)
{
i64 x;
scanner.scan(x);
fenwick.add(i, x);
}
for(int i = 1;i <= q;i++)
{
i64 op, l, r;
scanner.scan(op, l, r);
if(op == 0)
fenwick.add(++l, r);
else
printer.print(fenwick.Rangesum(++l, r)), printer.putchar('\n');
}
}#line 1 "test/library_checker/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 1 "head.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define CLOCK 1e3 * clock() / CLOCKS_PER_SEC
#line 2 "data_structure/1D-fenwick.hpp"
template<typename T>
struct Fenwick
{
const int n;
std::vector<T> a;
Fenwick(int _n) : n(_n), a(_n) {}
void add(int x, T v)
{
for(int i = x;i <= n;i += i & -i)
a[i] += v;
return;
}
T sum(int x)
{
T Ans = 0;
for(int i = x;i;i -= i & -i)
Ans += a[i];
return Ans;
}
T Rangesum(int l, int r) {return sum(r) - sum(l - 1);} // [l, r]
};
#line 2 "io/Scanner.hpp"
class Scanner
{
public:
Scanner(std::FILE *f = stdin, std::size_t enough_buffer_size = 1 << 25)
: f_(f), buffer_(new char[enough_buffer_size + 32]), buffer_head_(buffer_),
buffer_tail_(buffer_ + std::fread(buffer_, sizeof(char), enough_buffer_size + 32, f_)) {*buffer_tail_ = '\0';}
~Scanner() {delete[] buffer_;}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, bool>
scan(T &x)
{
x = 0;
while(*buffer_head_ != '-' && std::isspace(*buffer_head_))
++buffer_head_;
bool is_neg = *buffer_head_ == '-' && ++buffer_head_;
char *old_buffer_head = buffer_head_;
if(is_neg)
while(std::isdigit(*buffer_head_)) x = x * 10 - (*buffer_head_++ - '0');
else
while(std::isdigit(*buffer_head_)) x = x * 10 + (*buffer_head_++ - '0');
return buffer_head_ != old_buffer_head;
}
template<typename... T>
bool scan(T &...x)
{
return (... && scan(x));
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_tail_;
};
#line 2 "io/Printer.hpp"
class Printer
{
public:
Printer(std::FILE *f = stdout, std::size_t buffer_size = 100000)
: f_(f), buffer_(new char[buffer_size + 32]), buffer_head_(buffer_),
buffer_end_(buffer_ + buffer_size + 32), stk_(new char[32]), top_(stk_) {}
~Printer()
{
flush();
delete[] stk_;
delete[] buffer_;
}
void flush()
{
std::fwrite(buffer_, buffer_head_ - buffer_, sizeof(char), f_);
buffer_head_ = buffer_;
}
void putchar(char x)
{
if(buffer_end_ == buffer_head_)
flush();
*buffer_head_++ = x;
}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
if(x < 0)
{
putchar('-');
do
{
T y = x / 10;
*top_++ = y * 10 - x + '0';
x = y;
} while(x != 0);
}
else
{
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
}
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
void print(char x) {return this->putchar(x);}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_unsigned_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
template<typename... T>
void print(T... x)
{
return (..., print(x));
}
template<typename T>
void println(T x)
{
return this->print(x), this->putchar('\n');
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_end_, *stk_, *top_;
};
#line 6 "test/library_checker/point_add_range_sum.test.cpp"
using i64 = long long;
constexpr int mmax = 5E5 + 10;
Scanner scanner;
Printer printer;
Fenwick<i64> fenwick(mmax);
int main()
{
i64 n, q;
scanner.scan(n, q);
for(int i = 1;i <= n;i++)
{
i64 x;
scanner.scan(x);
fenwick.add(i, x);
}
for(int i = 1;i <= q;i++)
{
i64 op, l, r;
scanner.scan(op, l, r);
if(op == 0)
fenwick.add(++l, r);
else
printer.print(fenwick.Rangesum(++l, r)), printer.putchar('\n');
}
}