verify/yosupo/yosupo-point_add_range_sum-range-set-segment-tree.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• library/contest/template-minimal.hpp
• library/data-structures/1d-range-queries/range-set-segment-tree.hpp

Code

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

#include "../../library/contest/template-minimal.hpp"
#include "../../library/data-structures/1d-range-queries/range-set-segment-tree.hpp"

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<long long> a(n);
	RangeSetSeg<long long> seg; 
	seg.init(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i], seg.range_set(i, i, a[i]);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			seg.range_set(p, p, x + seg.qsum(p, p));
		} else {
			int l, r;
			cin >> l >> r;
			--r;
			cout << seg.qsum(l, r) << '\n';
		}
	}
	return 0;
}

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


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class T> struct RangeSetSeg {
	const T UNUSED = -1;
	std::vector<T> sum, lazy;
	int sz;

	// lazy stores what to set to

	void init(int sz_) {
		sz = 1;
		while (sz < sz_) sz *= 2;
		sum.assign(2 * sz, 0);
		lazy.assign(2 * sz, UNUSED);
	}

	void push(int ind, int L, int R) {
		if (L != R) {
			if(lazy[ind] != UNUSED){
				for(int i = 0; i < 2; i++){
					lazy[2 * ind + i] = lazy[ind];
				}
			}
		}
		if (lazy[ind] != UNUSED) sum[ind] = (R - L + 1) * lazy[ind];
		lazy[ind] = UNUSED;
	}

	void pull(int ind) { sum[ind] = sum[2 * ind] + sum[2 * ind + 1]; }

	void range_set(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
		if (R == -1) R += sz;
		push(ind, L, R);
		if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) {
			lazy[ind] = inc;
			push(ind, L, R); return;
		}
		int M = (L + R) / 2;
		range_set(lo, hi, inc, 2 * ind, L, M); range_set(lo, hi, inc, 2 * ind + 1, M + 1, R);
		pull(ind);
	}

	T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
		if (R == -1) R += sz;
		push(ind, L, R); if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return sum[ind];
		int M = (L + R) / 2;
		return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
	}
};

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<long long> a(n);
	RangeSetSeg<long long> seg; 
	seg.init(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i], seg.range_set(i, i, a[i]);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			seg.range_set(p, p, x + seg.qsum(p, p));
		} else {
			int l, r;
			cin >> l >> r;
			--r;
			cout << seg.qsum(l, r) << '\n';
		}
	}
	return 0;
}

Back to top page