This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum" #include <bits/stdc++.h> using namespace std; #include "../Fenwick/Fenwick.h" #include "../../buffered_reader.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n = IO::get<int>(); int q = IO::get<int>(); Fenwick<long long> f(n); REP(i,n) { int x = IO::get<int>(); f.update(i, x); } while (q--) { int l = IO::get<int>(); int r = IO::get<int>(); cout << f.get(l, r) << '\n'; } return 0; }
#line 1 "DataStructure/test/fenwick.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum" #include <bits/stdc++.h> using namespace std; #line 1 "DataStructure/Fenwick/Fenwick.h" // 1D Fenwick {{{ // 0 based index // // Tested: // - https://judge.yosupo.jp/problem/static_range_sum // - https://judge.yosupo.jp/problem/point_add_range_sum template< typename T // need to support operators + - > struct Fenwick { Fenwick(int _n) : n(_n), f(_n + 1) {} // a[u] += val void update(int u, T val) { assert(0 <= u && u < n); ++u; for (; u <= n; u += u & -u) { f[u] += val; } } // return a[0] + .. + a[u-1] T get(int u) const { assert(0 <= u && u <= n); T res = 0; for (; u > 0; u -= u & -u) { res += f[u]; } return res; } // return a[l] + .. + a[r-1] T get(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; // empty return get(r) - get(l); } void reset() { std::fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; }; // }}} #line 1 "buffered_reader.h" // Buffered reader {{{ namespace IO { const int BUFSIZE = 1<<14; char buf[BUFSIZE + 1], *inp = buf; bool reacheof; char get_char() { if (!*inp && !reacheof) { memset(buf, 0, sizeof buf); int tmp = fread(buf, 1, BUFSIZE, stdin); if (tmp != BUFSIZE) reacheof = true; inp = buf; } return *inp++; } template<typename T> T get() { int neg = 0; T res = 0; char c = get_char(); while (!std::isdigit(c) && c != '-' && c != '+') c = get_char(); if (c == '+') { neg = 0; } else if (c == '-') { neg = 1; } else res = c - '0'; c = get_char(); while (std::isdigit(c)) { res = res * 10 + (c - '0'); c = get_char(); } return neg ? -res : res; } }; // Helper methods int ri() { return IO::get<int>(); } // }}} #line 8 "DataStructure/test/fenwick.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n = IO::get<int>(); int q = IO::get<int>(); Fenwick<long long> f(n); REP(i,n) { int x = IO::get<int>(); f.update(i, x); } while (q--) { int l = IO::get<int>(); int r = IO::get<int>(); cout << f.get(l, r) << '\n'; } return 0; }