This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include "head.hpp"
#include "data_structure/1D-fenwick.hpp"
#include "io/Scanner_local.hpp"
#include "io/Printer_local.hpp"
#include "debug.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 l, r;
scanner.scan(l, r);
printer.println(fenwick.Rangesum(++l, r));
}
debug(fenwick.Rangesum(1, n));
}#line 1 "test/library_checker/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_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_local.hpp"
struct Scanner
{
template<typename T>
void scan(T &x)
{
std::cin >> x;
}
template<typename... T>
void scan(T& ...x)
{
((std::cin >> x), ...);
}
};
#line 2 "io/Printer_local.hpp"
struct Printer
{
template<typename T>
void print(T x)
{
std::cout << x;
}
void putchar(char x)
{
putchar(x);
}
template<typename T>
void println(T x)
{
std::cout << x << endl;
}
};
#line 2 "debug.hpp"
#line 4 "debug.hpp"
#include <type_traits>
#line 8 "debug.hpp"
namespace dbg {
// arithmetic
template <class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
void print(const T &x) {std::cerr << std::boolalpha << x;}
// string
void print(const std::string &x) {std::cerr << '\"' << x << '\"';}
// bitset
template <std::size_t N> void print(const std::bitset<N> &Bs) {std::cerr << Bs;}
// pair
template <class T, class U> void print(const std::pair<T, U> &p) {
std::cerr << "(";
print(p.first);
std::cerr << ", ";
print(p.second);
std::cerr << ")";
}
// tuple
template <class... Args> void print(const std::tuple<Args...> &t) {
std::cerr << "(";
std::apply([](auto &&... args) {((print(args), std::cerr << ", "), ...);}, t);
std::cerr << ")";
}
// Iterable
template <typename T, typename = std::void_t<>>
struct is_iterable : public std::false_type {};
template <typename T>
struct is_iterable<T, std::void_t<decltype(std::declval<T>().begin(),
std::declval<T>().end())>>
: public std::true_type {};
template <typename T>
using is_iterable_t = typename is_iterable<T>::type;
template <typename T>
inline constexpr bool is_iterable_v = is_iterable<T>::value;
template <class T, std::enable_if_t<dbg::is_iterable_v<T>, int> = 0>
void print(const T &v) {
int f = 0;
std::cerr << '{';
for (const auto &i : v) std::cerr << (f++ ? ", " : ""), print(i);
std::cerr << "}";
}
// Debug Mode
void debug_out() { std::cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
std::cerr << " ", print(H), debug_out(T...);
}
#define debug(...) \
std::cerr << __func__ << ":" << __LINE__ << " [" << #__VA_ARGS__ \
<< "] =", \
debug_out(__VA_ARGS__)
};
using namespace dbg;
//
//} // namespace dbg
/**
* Based on submission('https://codeforces.com/contest/1787/submission/191105890')
* ANSI Escape Sequences: https://gist.github.com/fnky/458719343aabd01cfb17a3a4f7296797
*/
#line 7 "test/library_checker/static_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 l, r;
scanner.scan(l, r);
printer.println(fenwick.Rangesum(++l, r));
}
debug(fenwick.Rangesum(1, n));
}