tests/bit.test.cpp

View this file on GitHub
Last update: 2024-02-01 17:09:56-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 "../content/data_structures/bit.h"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);
	
	int n, q;
	cin>>n>>q;
	
	bit<ll> t;
	t.init(n+1, 0, [](auto x, auto y){ return x+y;});
	
	for(int i = 1,a; i <= n; i++){
		cin>>a;
		t.update(i, a);
	}
	
	while(q--){
		int op;
		cin>>op;
		if(op == 0){
			int i, x;
			cin>>i>>x;
			t.update(i+1, x);
		}
		else{
			int l, r;
			cin>>l>>r;
			cout<<t.query(r)-t.query(l)<<'\n';
		}
	}
}

#line 1 "tests/bit.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/data_structures/bit.h"

/**
 * @brief Binary Indexed Tree
 * @docs docs/bit.md
 */

template<class T> struct bit{
	int SZ;
	vector<T> bit;
	function<T(T, T)> merge;
	
	void init(int n, T def, function<T(T, T)> f){
		SZ = n;
		bit.resize(SZ, def);
		merge = f;
	}
	void update(int i, T v){
		for(; i < SZ; i += i&-i)
			bit[i] = merge(bit[i], v);
	}
	T query(int i){
		T x = bit[0];
		for(; i; i -= i&-i)
			x = merge(x, bit[i]);
		return x;
	}
};

template<class T> struct range_bit{
	bit<T> T1, T2;
	function<T(T, T)> unmerge;

	void init(int n, T def, function<T(T, T)> f, function<T(T, T)> g){
		T1.init(n, def, f);
		T2.init(n, def, f);
		unmerge = g;
	}
	T query(int i){
		return i*T1.query(i)-T2.query(i);
	}
	T query(int l, int r){
		return unmerge(query(r), query(l-1));
	}
	void update(int l, int r, T v){
		T1.update(l, v);
		T1.update(r+1, -v);
		T2.update(l, v*(l-1));
		T2.update(r+1, -v*r);
	}
	void update(int l, T v){
		update(l, l, v);
	}
};
#line 3 "tests/bit.test.cpp"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);
	
	int n, q;
	cin>>n>>q;
	
	bit<ll> t;
	t.init(n+1, 0, [](auto x, auto y){ return x+y;});
	
	for(int i = 1,a; i <= n; i++){
		cin>>a;
		t.update(i, a);
	}
	
	while(q--){
		int op;
		cin>>op;
		if(op == 0){
			int i, x;
			cin>>i>>x;
			t.update(i+1, x);
		}
		else{
			int l, r;
			cin>>l>>r;
			cout<<t.query(r)-t.query(l)<<'\n';
		}
	}
}