test/fenwick_tree2.test.cpp

• View this file on GitHub
• Last update: 2023-02-01 12:02:26+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• fenwick_tree (一点加算、区間和取得) (src/dataStructure/fenwick_tree.hpp)
• fenwick tree add structure (src/utility/fenwick_tree/add.hpp)

Code

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

#include "../src/utility/fenwick_tree/add.hpp"
#include "../src/dataStructure/fenwick_tree.hpp"

#include <iostream>
#include <vector>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N, Q; std::cin >> N >> Q;
	std::vector a(N, 0LL);
	for (auto& ai : a) {
		std::cin >> ai;
	}
	zawa::fenwick_tree<zawa::add_structure<long long>> fen(a);
	for (int _ = 0 ; _ < Q ; _++) {
		int t; std::cin >> t;
		if (t == 0) {
			int p, x; std::cin >> p >> x;
			fen.add(p, x);
		}
		if (t == 1) {
			int l, r; std::cin >> l >> r;
			std::cout << fen.sum(l, r) << std::endl;
		}
	}
}

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

#line 2 "src/utility/fenwick_tree/add.hpp"

namespace zawa {

template <class dat_type>
struct add_structure {
	using T = dat_type;
	static constexpr T id = T{};
	static T add(const T& a, const T& b) {
		return a + b;
	}
	static T inverse(const T& a) {
		return -a;
	}
};

} // namespace zawa
#line 2 "src/dataStructure/fenwick_tree.hpp"

#include <vector>

namespace zawa {

template <class structure>
class fenwick_tree {
private:
	using T = typename structure::T;
	std::vector<T> dat;
	int pow_two;

	inline int lsb(int x) {
		return x & -x;
	}

	T sum(int r) {
		T res = 0;
		while (r > 0) {
			res = structure::add(res, dat[r]);
			r -= lsb(r);
		}
		return res;
	}
	
public:

	fenwick_tree(std::size_t n) : dat(n + 1, structure::id), pow_two(std::__lg(n) + 1) {}
	
	fenwick_tree(const std::vector<T>& A) : dat(A.size() + 1, structure::id), pow_two(std::__lg(A.size()) + 1) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			add(i, A[i]);
		}
	}


	T sum(int l, int r) {
		return structure::add(sum(r), structure::inverse(sum(l)));
	}

	void add(int pos, const T& v) {
		pos++;
		while (pos < (int)dat.size()) {
			dat[pos] = structure::add(dat[pos], v);
			pos += lsb(pos);
		}
	}

	int lower_bound(T val) {
		int res = 0;
		T now = structure::id;
		for (int x = (1 << pow_two) ; x > 0 ; x >>= 1) {
			if (res + x < (int)dat.size()) {
				T nxt = structure::add(now, dat[res + x]);
				if (nxt < val) {
					res += x;
					now = nxt;
				}
			}
		}
		return res;
	}
};

} // namespace zawa
#line 5 "test/fenwick_tree2.test.cpp"

#include <iostream>
#line 8 "test/fenwick_tree2.test.cpp"

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N, Q; std::cin >> N >> Q;
	std::vector a(N, 0LL);
	for (auto& ai : a) {
		std::cin >> ai;
	}
	zawa::fenwick_tree<zawa::add_structure<long long>> fen(a);
	for (int _ = 0 ; _ < Q ; _++) {
		int t; std::cin >> t;
		if (t == 0) {
			int p, x; std::cin >> p >> x;
			fen.add(p, x);
		}
		if (t == 1) {
			int l, r; std::cin >> l >> r;
			std::cout << fen.sum(l, r) << std::endl;
		}
	}
}

Back to top page