test/yosupo/point_add_range_sum.test.cpp

View this file on GitHub
Last update: 2021-02-13 18:30:55+09:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

src/FenwickTree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include "../../src/FenwickTree.hpp"

#include <iostream>
#include <iomanip>

using namespace std;
using lint = long long;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int n, q;
	cin >> n >> q;

	FenwickTree<lint> ft(n, 0);
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		ft.set(i, a);
	}

	for (int i = 0; i < q; i++) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c) {
			cout << ft.sum(x, y) << "\n";
		}
		else {
			ft.add(x, y);
		}
	}

	return 0;
}

#line 1 "test/yosupo/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#line 2 "src/FenwickTree.hpp"

#include <vector>

using namespace std;

template<class T>
class FenwickTree {
public:
    explicit FenwickTree(int sz, T &&x = T{}) : n(sz), bit(n + 1) {
        for (int i = 0; i < n; i++) add(i, x);
    }

    void add(int k, const T &x) { for (; k < n; k |= k + 1) bit[k] += x; }
    void set(int k, const T &x) { add(k, x - sum(k, k + 1)); }

    [[nodiscard]] T sum(int k) const {
        T res = 0;
        for (k--; k >= 0; k = (k & (k + 1)) - 1) res += bit[k];
        return res;
    }
    [[nodiscard]] T sum(int l, int r) const { return sum(r) - sum(l); }

private:
    int n;
    vector<T> bit;
};
#line 4 "test/yosupo/point_add_range_sum.test.cpp"

#include <iostream>
#include <iomanip>

using namespace std;
using lint = long long;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int n, q;
	cin >> n >> q;

	FenwickTree<lint> ft(n, 0);
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		ft.set(i, a);
	}

	for (int i = 0; i < q; i++) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c) {
			cout << ft.sum(x, y) << "\n";
		}
		else {
			ft.add(x, y);
		}
	}

	return 0;
}