Submit Info #2987

Problem Lang User Status Time Memory
Point Add Range Sum cpp niuez AC 115 ms 16.26 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 0.60 MiB
max_random_00 AC 113 ms 16.26 MiB
max_random_01 AC 115 ms 16.25 MiB
max_random_02 AC 114 ms 16.26 MiB
max_random_03 AC 103 ms 16.26 MiB
max_random_04 AC 98 ms 16.18 MiB
random_00 AC 80 ms 14.64 MiB
random_01 AC 82 ms 15.25 MiB
random_02 AC 53 ms 4.75 MiB
random_03 AC 24 ms 12.14 MiB
random_04 AC 32 ms 11.51 MiB

#include <bits/stdc++.h> using namespace std; using i64 = long long; struct segment_tree { using T = i64; static T ope(const T& a, const T& b) { return a + b; } static T ide() { return 0; } i64 n; vector<T> node; segment_tree(const vector<T>& init) { n = 1; while(n < init.size()) n *= 2; node.resize(2 * n, ide()); for(int i = 0;i < init.size();i++) node[i + n] = init[i]; for(int i = n - 1; i >= 1;i--) node[i] = ope(node[i * 2], node[i * 2 + 1]); } void update(i64 i, T x) { i += n; node[i] += x; while(i > 1) { i = i / 2; node[i] = ope(node[i * 2], node[i * 2 + 1]); } } /* [l, r) */ T sum(i64 l, i64 r) { T lx = ide(); T rx = ide(); l += n; r += n - 1; while(l < r) { if(l & 1) { lx = ope(lx, node[l]); } if(!(r & 1)) { rx = ope(node[r], rx); } l = (l + 1) >> 1; r = (r - 1) >> 1; } if(l == r) { lx = ope(lx, node[l]); } return ope(lx, rx); } }; #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; } #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) 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]; segment_tree seg(init); i64 q, a, b; while(Q--) { fin >> q >> a >> b; if(q == 0) { seg.update(a, b); } else { fout << seg.sum(a, b) << '\n'; } } }