verify/yosupo/yosupo-point_add_range_sum-fenwick-tree.test.cpp

View this file on GitHub
Last update: 2023-01-08 14:16:34-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/fenwick-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);
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	FenwickTree<long long> F; 
	F.init(a);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, x;
			cin >> p >> x;
			F.add(p, x);
		} else {
			int l, r;
			cin >> l >> r;
			--r;
			cout << F.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 FenwickTree {
  std::vector<T> fwt;
  int n;

  FenwickTree() = default;
  FenwickTree(int n) { init(n); }
  FenwickTree(std::vector<T>& a) { init(a); }

  void init(int n_) {
    n = n_;
    fwt.assign(n, 0);
  }

  void init(std::vector<T>& a) {
    n = (int)a.size();
    fwt.assign(n, 0);
    for (int i = 0; i < (int)a.size(); i++) {
      add(i, a[i]);
    }
  }

  T sum(int r) {
    T ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ret += fwt[r];
    return ret;
  }

  T query(int l, int r) { return sum(r) - sum(l - 1); }

  void add(int idx, T delta) {
    for (; idx < n; idx = idx | (idx + 1)) fwt[idx] += delta;
  }
};

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