12tqian's Competitive Programming Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub 12tqian/cp-library

:heavy_check_mark: verify/yosupo/yosupo-point_add_range_sum-sparse-segment-tree.test.cpp

Depends on

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/sparse-segment-tree.hpp"

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	typedef long long ll;
	int n, q; 
	cin >> n >> q;
	vector<ll> a(n);
	Node<ll> seg;
	for (int i = 0; i < n; i++) 
		cin >> a[i], seg.upd(i, a[i]);
	while (q--) {
		int t; cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			seg.upd(p, x);
		} else {
			int l, r; cin >> l >> r;
			cout << seg.query(l, r - 1) << '\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;

// bump allocator


static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}

const int SZ = 1 << 30;

template <class T> struct Node {
	T val = 0; 
	Node<T>* c[2];
	Node() { c[0] = c[1] = NULL; }

	void upd(int ind, T v, int L = 0, int R = SZ - 1) { // add v

		if (L == ind && R == ind) { val += v; return; }
		int M = (L + R) / 2;
		if (ind <= M) {
			if (!c[0]) c[0] = new Node();
			c[0]->upd(ind, v, L, M);
		} else {
			if (!c[1]) c[1] = new Node();
			c[1]->upd(ind, v, M + 1, R);
		}
		val = 0; 
		for (int i = 0; i < 2; i++)
			if (c[i]) val += c[i]->val;
	}

	T query(int lo, int hi, int L = 0, int R = SZ - 1) { // query sum of segment

		if (hi < L || R < lo) return 0;
		if (lo <= L && R <= hi) return val;
		int M = (L + R) / 2; 
		T res = 0;
		if (c[0]) res += c[0]->query(lo, hi, L, M);
		if (c[1]) res += c[1]->query(lo, hi, M + 1, R);
		return res;
	}

	void update_2d(int ind, Node* c0, Node* c1, int L = 0, int R = SZ - 1) { // for 2D segtree

		if (L != R)	 {
			int M = (L + R) / 2;
			if (ind <= M) {
				if (!c[0]) c[0] = new Node();
				c[0]->update_2d(ind, (c0 ? c0->c[0] : NULL), (c1 ? c1->c[0] : NULL), L, M);
			} else {
				if (!c[1]) c[1] = new Node();
				c[1]->update_2d(ind, (c0 ? c0->c[1] : NULL), (c1 ? c1->c[1] : NULL), M + 1, R);
			}
		} 
		val = (c0 ? c0->val : 0) + (c1 ? c1->val : 0);
	}
};

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	typedef long long ll;
	int n, q; 
	cin >> n >> q;
	vector<ll> a(n);
	Node<ll> seg;
	for (int i = 0; i < n; i++) 
		cin >> a[i], seg.upd(i, a[i]);
	while (q--) {
		int t; cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			seg.upd(p, x);
		} else {
			int l, r; cin >> l >> r;
			cout << seg.query(l, r - 1) << '\n';
		}
	}
	return 0;
}
Back to top page