Initial commit

1 files changed, 50 insertions, 0 deletions

diff --git a/05_range_queries/dynamic_range_sum_queries_1648.cpp b/05_range_queries/dynamic_range_sum_queries_1648.cpp
new file mode 100644
index 0000000..ceb6b0c
--- /dev/null
+++ b/05_range_queries/dynamic_range_sum_queries_1648.cpp
@@ -0,0 +1,50 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+class SumFenwickTree {
+public:
+        SumFenwickTree(int n) : a(n+1) {}
+        long long sum(int l, int r) const { return psum(r) - psum(l-1); }
+        void update(int k, long long u) { add(k, u - sum(k, k));}
+
+private:
+        std::vector<long long> a;
+
+        static int lsb(int i) { return i & -i; }
+
+        long long psum(int i) const {
+                long long s = 0;
+                while (i > 0) {
+                        s += a[i];
+                        i -= lsb(i);
+                }
+                return s;
+        }
+
+        void add(int k, long long d) {
+                while (k < (int)a.size()) {
+                        a[k] += d;
+                        k += lsb(k);
+                }
+        }
+};
+
+int main() {
+        size_t n, q;
+        std::cin >> n >> q;
+        SumFenwickTree t(n);
+        for (size_t i = 0; i < n; i++) {
+                long long x;
+                std::cin >> x;
+                t.update(i+1, x);
+        }
+        for (size_t i = 0; i < q; i++) {
+                long long x, k, u;
+                std::cin >> x >> k >> u;
+                if (x == 1)
+                        t.update(k, u);
+                else
+                        std::cout << t.sum(k, u) << "\n";
+        }
+}