cp-book

ecnerwala's competitive programming library

View the Project on GitHub ecnerwala/cp-book

:heavy_check_mark: verify/point_add_range_sum.test.cpp

View this file on GitHub · Last update: 2026-07-25 01:16:11-07:00

Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum

#include <bits/stdc++.h>
#include <cassert>

#include "seg_tree.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N, Q; std::cin >> N >> Q;
	seg_tree::in_order_layout layout(N);
	std::vector<int64_t> seg(2*N);
	for (int i = 0; i < N; i++) {
		int64_t x; std::cin >> x;
		seg[layout.get_point(i)] = x;
	}
	for (seg_tree::point a(N-1); a >= 1; a--) {
		seg[a] = seg[a.c(0)] + seg[a.c(1)];
	}
	for (int q = 0; q < Q; q++) {
		int op; std::cin >> op;
		if (op == 0) {
			int p; int64_t x; std::cin >> p >> x;
			layout.get_point(p).for_each_up([&](seg_tree::point a) {
				seg[a] += x;
			});
		} else if (op == 1) {
			int l, r; std::cin >> l >> r;
			int64_t ans = 0;
			layout.get_range(l, r).for_each([&](seg_tree::point a) {
				ans += seg[a];
			});
			std::cout << ans << '\n';
		} else assert(false);
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/point_add_range_sum.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum

#line 5 "verify/point_add_range_sum.test.cpp"

#line 4 "src/seg_tree.hpp"

namespace seg_tree {

// Floor of log_2(a); index of highest 1-bit
inline int floor_log_2(int a) {
	return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}

inline int ceil_log_2(int a) {
	return a ? floor_log_2(2*a-1) : -1;
}

inline int next_pow_2(int a) {
	return 1 << ceil_log_2(a);
}

struct point {
	int a;
	point() : a(0) {}
	explicit point(int a_) : a(a_) { assert(a >= -1); }

	explicit operator bool () { return bool(a); }

	// This is useful so you can directly do array indices
	/* implicit */ operator int() const { return a; }

	point c(bool z) const {
		return point((a<<1)|z);
	}

	point operator [] (bool z) const {
		return c(z);
	}

	point p() const {
		return point(a>>1);
	}

	friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }

	template <typename F> void for_each(F f) const {
		for (int v = a; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	template <typename F> void for_each_down(F f) const {
		// strictly greater than 0
		for (int L = floor_log_2(a); L >= 0; L--) {
			f(point(a >> L));
		}
	}

	template <typename F> void for_each_up(F f) const {
		for (int v = a; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	template <typename F> void for_parents_down(F f) const {
		// strictly greater than 0
		for (int L = floor_log_2(a); L > 0; L--) {
			f(point(a >> L));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		for (int v = a >> 1; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	point& operator ++ () { ++a; return *this; }
	point operator ++ (int) { return point(a++); }
	point& operator -- () { --a; return *this; }
	point operator -- (int) { return point(a--); }
};

struct range {
	int a, b;
	range() : a(1), b(1) {}
	range(int a_, int b_) : a(a_), b(b_) {
		assert(1 <= a && a <= b && b <= 2 * a);
	}
	explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}

	explicit operator std::array<int, 2>() const {
		return {a,b};
	}

	const int& operator[] (bool z) const {
		return z ? b : a;
	}

	friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }

	// Iterate over the range from outside-in.
	//   Calls f(point a)
	template <typename F> void for_each(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++));
			if (y & 1) f(point(--y));
		}
	}

	// Iterate over the range from outside-in.
	//   Calls f(point a, bool is_right)
	template <typename F> void for_each_with_side(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++), false);
			if (y & 1) f(point(--y), true);
		}
	}

	// Iterate over the range from left to right.
	//    Calls f(point)
	template <typename F> void for_each_l_to_r(F f) const {
		int anc_depth = floor_log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = (-a) & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point(((a-1) >> i) + 1));
		}
		for (int v = b & anc_msk; v; ) {
			int i = floor_log_2(v);
			f(point((b >> i) - 1));
			v ^= (1 << i);
		}
	}

	// Iterate over the range from right to left.
	//    Calls f(point)
	template <typename F> void for_each_r_to_l(F f) const {
		int anc_depth = floor_log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = b & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point((b >> i) - 1));
		}
		for (int v = (-a) & anc_msk; v; ) {
			int i = floor_log_2(v);
			f(point(((a-1) >> i) + 1));
			v ^= (1 << i);
		}
	}

	template <typename F> void for_parents_down(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = floor_log_2((x-1) ^ y);
		for (int i = floor_log_2(x); i > dx; i--) {
			f(point(x >> i));
		}
		for (int i = anc_depth; i > dy; i--) {
			f(point(y >> i));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = floor_log_2((x-1) ^ y);
		for (int i = dx+1; i <= anc_depth; i++) {
			f(point(x >> i));
		}
		for (int v = y >> (dy+1); v; v >>= 1) {
			f(point(v));
		}
	}
};

struct in_order_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N, S;
	in_order_layout() : N(0), S(0) {}
	in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		a += S;
		return point(a >= 2 * N ? a - N : a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		a += S, b += S;
		return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return (a < S ? a + N : a) - S;
	}

	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
	}

	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
		int x = (2*a+1) << l;
		assert(S <= x && x < 2*S);
		return (x >= 2 * N ? (x>>1) + N : x) - S;
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		return bounds[1] - bounds[0];
	}
};

struct circular_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N;
	circular_layout() : N(0) {}
	circular_layout(int N_) : N(N_) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		return point(N + a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		return range(N + a, N + b);
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return a - N;
	}

	// Returns {x,y} so that 0 <= x < N and 1 <= y <= N
	// If the point is non-wrapping, then 0 <= x < y <= N
	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int S = next_pow_2(N);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
	}

	// Returns the split point of the node, such that 1 <= s <= N.
	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		return get_node_bounds(pt.c(0))[1];
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		int r = bounds[1] - bounds[0];
		return r > 0 ? r : r + N;
	}
};

} // namespace seg_tree
#line 7 "verify/point_add_range_sum.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N, Q; std::cin >> N >> Q;
	seg_tree::in_order_layout layout(N);
	std::vector<int64_t> seg(2*N);
	for (int i = 0; i < N; i++) {
		int64_t x; std::cin >> x;
		seg[layout.get_point(i)] = x;
	}
	for (seg_tree::point a(N-1); a >= 1; a--) {
		seg[a] = seg[a.c(0)] + seg[a.c(1)];
	}
	for (int q = 0; q < Q; q++) {
		int op; std::cin >> op;
		if (op == 0) {
			int p; int64_t x; std::cin >> p >> x;
			layout.get_point(p).for_each_up([&](seg_tree::point a) {
				seg[a] += x;
			});
		} else if (op == 1) {
			int l, r; std::cin >> l >> r;
			int64_t ans = 0;
			layout.get_range(l, r).for_each([&](seg_tree::point a) {
				ans += seg[a];
			});
			std::cout << ans << '\n';
		} else assert(false);
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/seg_tree.hpp
namespace seg_tree{
inline int floor_log_2(int a){
return a?(8*sizeof(a))-1-__builtin_clz(a):-1;
}
inline int ceil_log_2(int a){
return a?floor_log_2(2*a-1):-1;
}
inline int next_pow_2(int a){
return 1<<ceil_log_2(a);
}
struct point{
int a;
point():a(0){}
explicit point(int a_):a(a_){assert(a>=-1);}
explicit operator bool(){return bool(a);}
operator int()const{return a;}
point c(bool z)const{
return point((a<<1)|z);
}
point operator[](bool z)const{
return c(z);
}
point p()const{
return point(a>>1);
}
friend std::ostream&operator<<(std::ostream&o,const point&p){return o<<int(p);}
template<typename F>void for_each(F f)const{
for(int v=a;v>0;v>>=1){
f(point(v));
}
}
template<typename F>void for_each_down(F f)const{
for(int L=floor_log_2(a);L>=0;L--){
f(point(a>>L));
}
}
template<typename F>void for_each_up(F f)const{
for(int v=a;v>0;v>>=1){
f(point(v));
}
}
template<typename F>void for_parents_down(F f)const{
for(int L=floor_log_2(a);L>0;L--){
f(point(a>>L));
}
}
template<typename F>void for_parents_up(F f)const{
for(int v=a>>1;v>0;v>>=1){
f(point(v));
}
}
point&operator++(){++a;return*this;}
point operator++(int){return point(a++);}
point&operator--(){--a;return*this;}
point operator--(int){return point(a--);}
};
struct range{
int a,b;
range():a(1),b(1){}
range(int a_,int b_):a(a_),b(b_){
assert(1<=a&&a<=b&&b<=2*a);
}
explicit range(std::array<int,2>r):range(r[0],r[1]){}
explicit operator std::array<int,2>()const{
return{a,b};
}
const int&operator[](bool z)const{
return z?b:a;
}
friend std::ostream&operator<<(std::ostream&o,const range&r){return o<<"["<<r.a<<".."<<r.b<<")";}
template<typename F>void for_each(F f)const{
for(int x=a,y=b;x<y;x>>=1,y>>=1){
if(x&1)f(point(x++));
if(y&1)f(point(--y));
}
}
template<typename F>void for_each_with_side(F f)const{
for(int x=a,y=b;x<y;x>>=1,y>>=1){
if(x&1)f(point(x++),false);
if(y&1)f(point(--y),true);
}
}
template<typename F>void for_each_l_to_r(F f)const{
int anc_depth=floor_log_2((a-1)^b);
int anc_msk=(1<<anc_depth)-1;
for(int v=(-a)&anc_msk;v;v&=v-1){
int i=__builtin_ctz(v);
f(point(((a-1)>>i)+1));
}
for(int v=b&anc_msk;v;){
int i=floor_log_2(v);
f(point((b>>i)-1));
v^=(1<<i);
}
}
template<typename F>void for_each_r_to_l(F f)const{
int anc_depth=floor_log_2((a-1)^b);
int anc_msk=(1<<anc_depth)-1;
for(int v=b&anc_msk;v;v&=v-1){
int i=__builtin_ctz(v);
f(point((b>>i)-1));
}
for(int v=(-a)&anc_msk;v;){
int i=floor_log_2(v);
f(point(((a-1)>>i)+1));
v^=(1<<i);
}
}
template<typename F>void for_parents_down(F f)const{
int x=a,y=b;
if((x^y)>x){x<<=1,std::swap(x,y);}
int dx=__builtin_ctz(x);
int dy=__builtin_ctz(y);
int anc_depth=floor_log_2((x-1)^y);
for(int i=floor_log_2(x);i>dx;i--){
f(point(x>>i));
}
for(int i=anc_depth;i>dy;i--){
f(point(y>>i));
}
}
template<typename F>void for_parents_up(F f)const{
int x=a,y=b;
if((x^y)>x){x<<=1,std::swap(x,y);}
int dx=__builtin_ctz(x);
int dy=__builtin_ctz(y);
int anc_depth=floor_log_2((x-1)^y);
for(int i=dx+1;i<=anc_depth;i++){
f(point(x>>i));
}
for(int v=y>>(dy+1);v;v>>=1){
f(point(v));
}
}
};
struct in_order_layout{
using point=seg_tree::point;
using range=seg_tree::range;
int N,S;
in_order_layout():N(0),S(0){}
in_order_layout(int N_):N(N_),S(N?next_pow_2(N):0){}
point get_point(int a)const{
assert(0<=a&&a<N);
a+=S;
return point(a>=2*N?a-N:a);
}
range get_range(int a,int b)const{
assert(0<=a&&a<=b&&b<=N);
if(N==0)return range();
a+=S,b+=S;
return range((a>=2*N?2*(a-N):a),(b>=2*N?2*(b-N):b));
}
range get_range(std::array<int,2>p)const{
return get_range(p[0],p[1]);
}
int get_leaf_index(point pt)const{
int a=int(pt);
assert(N<=a&&a<2*N);
return(a<S?a+N:a)-S;
}
std::array<int,2>get_node_bounds(point pt)const{
int a=int(pt);
assert(1<=a&&a<2*N);
int l=__builtin_clz(a)-__builtin_clz(2*N-1);
int x=a<<l,y=(a+1)<<l;
assert(S<=x&&x<y&&y<=2*S);
return{(x>=2*N?(x>>1)+N:x)-S,(y>=2*N?(y>>1)+N:y)-S};
}
int get_node_split(point pt)const{
int a=int(pt);
assert(1<=a&&a<N);
int l=__builtin_clz(2*a+1)-__builtin_clz(2*N-1);
int x=(2*a+1)<<l;
assert(S<=x&&x<2*S);
return(x>=2*N?(x>>1)+N:x)-S;
}
int get_node_size(point pt)const{
auto bounds=get_node_bounds(pt);
return bounds[1]-bounds[0];
}
};
struct circular_layout{
using point=seg_tree::point;
using range=seg_tree::range;
int N;
circular_layout():N(0){}
circular_layout(int N_):N(N_){}
point get_point(int a)const{
assert(0<=a&&a<N);
return point(N+a);
}
range get_range(int a,int b)const{
assert(0<=a&&a<=b&&b<=N);
if(N==0)return range();
return range(N+a,N+b);
}
range get_range(std::array<int,2>p)const{
return get_range(p[0],p[1]);
}
int get_leaf_index(point pt)const{
int a=int(pt);
assert(N<=a&&a<2*N);
return a-N;
}
std::array<int,2>get_node_bounds(point pt)const{
int a=int(pt);
assert(1<=a&&a<2*N);
int l=__builtin_clz(a)-__builtin_clz(2*N-1);
int S=next_pow_2(N);
int x=a<<l,y=(a+1)<<l;
assert(S<=x&&x<y&&y<=2*S);
return{(x>=2*N?x>>1:x)-N,(y>2*N?y>>1:y)-N};
}
int get_node_split(point pt)const{
int a=int(pt);
assert(1<=a&&a<N);
return get_node_bounds(pt.c(0))[1];
}
int get_node_size(point pt)const{
auto bounds=get_node_bounds(pt);
int r=bounds[1]-bounds[0];
return r>0?r:r+N;
}
};
}
// verify/point_add_range_sum.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
int N,Q;std::cin>>N>>Q;
seg_tree::in_order_layout layout(N);
std::vector<int64_t>seg(2*N);
for(int i=0;i<N;i++){
int64_t x;std::cin>>x;
seg[layout.get_point(i)]=x;
}
for(seg_tree::point a(N-1);a>=1;a--){
seg[a]=seg[a.c(0)]+seg[a.c(1)];
}
for(int q=0;q<Q;q++){
int op;std::cin>>op;
if(op==0){
int p;int64_t x;std::cin>>p>>x;
layout.get_point(p).for_each_up([&](seg_tree::point a){
seg[a]+=x;
});
}else if(op==1){
int l,r;std::cin>>l>>r;
int64_t ans=0;
layout.get_range(l,r).for_each([&](seg_tree::point a){
ans+=seg[a];
});
std::cout<<ans<<'\n';
}else assert(false);
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env Name Status Elapsed Memory
g++-sanitizer example_00 :heavy_check_mark: AC 14 ms 8 MB
g++-sanitizer max_random_00 :heavy_check_mark: AC 257 ms 19 MB
g++-sanitizer max_random_01 :heavy_check_mark: AC 232 ms 19 MB
g++-sanitizer max_random_02 :heavy_check_mark: AC 245 ms 19 MB
g++-sanitizer max_random_03 :heavy_check_mark: AC 224 ms 19 MB
g++-sanitizer max_random_04 :heavy_check_mark: AC 229 ms 19 MB
g++-sanitizer random_00 :heavy_check_mark: AC 186 ms 17 MB
g++-sanitizer random_01 :heavy_check_mark: AC 222 ms 19 MB
g++-sanitizer random_02 :heavy_check_mark: AC 136 ms 11 MB
g++-sanitizer random_03 :heavy_check_mark: AC 60 ms 18 MB
g++-sanitizer random_04 :heavy_check_mark: AC 72 ms 15 MB
g++-sanitizer small_00 :heavy_check_mark: AC 16 ms 8 MB
g++-sanitizer small_01 :heavy_check_mark: AC 16 ms 8 MB
g++-sanitizer small_02 :heavy_check_mark: AC 15 ms 8 MB
g++-sanitizer small_03 :heavy_check_mark: AC 16 ms 8 MB
g++-sanitizer small_04 :heavy_check_mark: AC 11 ms 8 MB
g++-sanitizer small_05 :heavy_check_mark: AC 13 ms 8 MB
g++-sanitizer small_06 :heavy_check_mark: AC 17 ms 8 MB
g++-sanitizer small_07 :heavy_check_mark: AC 13 ms 8 MB
g++-sanitizer small_08 :heavy_check_mark: AC 17 ms 8 MB
g++-sanitizer small_09 :heavy_check_mark: AC 18 ms 8 MB
g++ example_00 :heavy_check_mark: AC 2 ms 4 MB
g++ max_random_00 :heavy_check_mark: AC 164 ms 11 MB
g++ max_random_01 :heavy_check_mark: AC 164 ms 11 MB
g++ max_random_02 :heavy_check_mark: AC 171 ms 11 MB
g++ max_random_03 :heavy_check_mark: AC 171 ms 11 MB
g++ max_random_04 :heavy_check_mark: AC 166 ms 11 MB
g++ random_00 :heavy_check_mark: AC 131 ms 10 MB
g++ random_01 :heavy_check_mark: AC 144 ms 11 MB
g++ random_02 :heavy_check_mark: AC 97 ms 4 MB
g++ random_03 :heavy_check_mark: AC 38 ms 10 MB
g++ random_04 :heavy_check_mark: AC 45 ms 8 MB
g++ small_00 :heavy_check_mark: AC 3 ms 4 MB
g++ small_01 :heavy_check_mark: AC 2 ms 4 MB
g++ small_02 :heavy_check_mark: AC 2 ms 4 MB
g++ small_03 :heavy_check_mark: AC 3 ms 4 MB
g++ small_04 :heavy_check_mark: AC 2 ms 4 MB
g++ small_05 :heavy_check_mark: AC 3 ms 4 MB
g++ small_06 :heavy_check_mark: AC 2 ms 4 MB
g++ small_07 :heavy_check_mark: AC 2 ms 4 MB
g++ small_08 :heavy_check_mark: AC 2 ms 4 MB
g++ small_09 :heavy_check_mark: AC 2 ms 4 MB
Back to top page