verify/yosupo/yosupo-point_add_range_sum-point-update-segment-tree.test.cpp

View this file on GitHub
Last update: 2023-01-08 15:53:16-05:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

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

int main() {
	using namespace std;
	cin.tie(0)->sync_with_stdio(0);
	int n, q; 
	cin >> n >> q;
	vector<long long> a(n);
	SegmentTree<long long> seg; 
	seg.init(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i], seg.add(i, a[i]);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			seg.add(p, x);
		} else {
			int l, r;
			cin >> l >> r;
			--r;
			cout << seg.query(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 SegmentTree {
  const T ID = 0;

  T comb(T a, T b) { return a + b; }

  int n;
  std::vector<T> seg;

  SegmentTree() = default;
  SegmentTree(int n) { init(n); }

  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }

  void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }

  void upd(int p, T val) {
    seg[p += n] = val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  void add(int p, T val) {
    seg[p += n] += val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  T query(int l, int r) {
    T ra = ID, rb = ID;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ra = comb(ra, seg[l++]);
      if (r & 1) rb = comb(seg[--r], rb);
    }
    return comb(ra, rb);
  }
};

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