Submit Info #2990

Problem Lang User Status Time Memory
Point Add Range Sum cpp niuez AC 96 ms 12.02 MiB

ケース詳細
Name Status Time Memory
example_00 AC 8 ms 0.64 MiB
max_random_00 AC 95 ms 12.00 MiB
max_random_01 AC 89 ms 12.00 MiB
max_random_02 AC 93 ms 12.00 MiB
max_random_03 AC 96 ms 12.02 MiB
max_random_04 AC 92 ms 12.00 MiB
random_00 AC 73 ms 9.59 MiB
random_01 AC 79 ms 10.75 MiB
random_02 AC 39 ms 4.22 MiB
random_03 AC 23 ms 7.38 MiB
random_04 AC 28 ms 5.51 MiB
small_00 AC 5 ms 0.55 MiB
small_01 AC 5 ms 0.62 MiB
small_02 AC 8 ms 0.62 MiB
small_03 AC 6 ms 0.62 MiB
small_04 AC 5 ms 0.63 MiB
small_05 AC 5 ms 0.62 MiB
small_06 AC 7 ms 0.66 MiB
small_07 AC 7 ms 0.62 MiB
small_08 AC 5 ms 0.62 MiB
small_09 AC 6 ms 0.67 MiB

#include <vector> #include <iostream> using i64 = long long; template<class AbelianMonoid, class Ope, const AbelianMonoid& Ide> struct fenwick_tree { using value_type = AbelianMonoid; i64 n; std::vector<value_type> node; Ope ope; fenwick_tree(i64 n_): n(n_), node(n + 1, Ide) {} fenwick_tree(const std::vector<value_type>& init): n(init.size()), node(n + 1, Ide) { for(i64 i = 0;i < init.size(); i++) node[i + 1] = init[i]; for(i64 i = 1;i < n;i++) node[i + (i & -i)] = ope(node[i + (i & -i)], node[i]); } void modify(i64 i, value_type x) { i++; while(i <= n) { node[i] = ope(node[i], x); i += (i & -i); } } // [0, i) value_type sum(i64 i) const { value_type ret = Ide; while(i > 0) { ret = ope(ret, node[i]); i -= i & (-i); } return ret; } }; #include <cstdio> namespace niu { char cur; struct FIN { static inline bool is_blank(char c) { return c <= ' '; } inline char next() { return cur = getc_unlocked(stdin); } inline char peek() { return cur; } inline void skip() { while(is_blank(next())){} } #define intin(inttype) \ FIN& operator>>(inttype& n) { \ bool sign = 0; \ n = 0; \ skip(); \ while(!is_blank(peek())) { \ if(peek() == '-') sign = 1; \ else n = (n << 1) + (n << 3) + (peek() & 0b1111); \ next(); \ } \ if(sign) n = -n; \ return *this; \ } intin(int) intin(long long) } fin; char tmp[128]; struct FOUT { static inline bool is_blank(char c) { return c <= ' '; } inline void push(char c) { putc_unlocked(c, stdout); } FOUT& operator<<(char c) { push(c); return *this; } FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; } #define intout(inttype) \ FOUT& operator<<(inttype n) { \ if(n) { \ char* p = tmp + 127; bool neg = 0; \ if(n < 0) neg = 1, n = -n; \ while(n) *--p = (n % 10) | 0b00110000, n /= 10; \ if(neg) *--p = '-'; \ return (*this) << p; \ } \ else { \ push('0'); \ return *this; \ } \ } intout(int) intout(long long) } fout; } #include <functional> #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) const i64 plus_ide = 0; int main() { using niu::fout; using niu::fin; int N, Q; fin >> N >> Q; std::vector<i64> init(N); rep(i,0,N) fin >> init[i]; fenwick_tree<i64, std::plus<i64>, plus_ide> fen(init); i64 q, a, b; while(Q--) { fin >> q >> a >> b; if(q == 0) { fen.modify(a, b); } else { fout << fen.sum(b) - fen.sum(a) << '\n'; } } }