dynamic_range_sum_queries_1648.cpp (877B)
1 #include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 class SumFenwickTree { 6 public: 7 SumFenwickTree(int n) : a(n+1) {} 8 long long sum(int l, int r) const { return psum(r) - psum(l-1); } 9 void update(int k, long long u) { add(k, u - sum(k, k));} 10 11 private: 12 std::vector<long long> a; 13 14 static int lsb(int i) { return i & -i; } 15 16 long long psum(int i) const { 17 long long s = 0; 18 while (i > 0) { 19 s += a[i]; 20 i -= lsb(i); 21 } 22 return s; 23 } 24 25 void add(int k, long long d) { 26 while (k < (int)a.size()) { 27 a[k] += d; 28 k += lsb(k); 29 } 30 } 31 }; 32 33 int main() { 34 size_t n, q; 35 std::cin >> n >> q; 36 SumFenwickTree t(n); 37 for (size_t i = 0; i < n; i++) { 38 long long x; 39 std::cin >> x; 40 t.update(i+1, x); 41 } 42 for (size_t i = 0; i < q; i++) { 43 long long x, k, u; 44 std::cin >> x >> k >> u; 45 if (x == 1) 46 t.update(k, u); 47 else 48 std::cout << t.sum(k, u) << "\n"; 49 } 50 }