CP-Algorithms Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
cp-algo/structures/segtree.hpp
- View this file on GitHub
- Last update: 2026-10-16 14:16:08+02:00
- Include:
#include "cp-algo/structures/segtree.hpp"
Depends on
Verified with
- Range Affine Range Sum (verify/structures/segtree/range_affine_range_sum.test.cpp)
- Range Chmin Chmax Add Range Sum (verify/structures/segtree/range_chmin_chmax_add_range_sum.test.cpp)
Code
#ifndef CP_ALGO_STRUCTURES_SEGMENT_TREE_HPP
#define CP_ALGO_STRUCTURES_SEGMENT_TREE_HPP
#include "../util/big_alloc.hpp"
#include <vector>
#include <numeric>
namespace cp_algo::structures {
template<typename meta>
struct segtree_t {
const size_t N;
big_vector<meta> _meta;
segtree_t(size_t n): N(n), _meta(4 * N) {}
segtree_t(big_vector<meta> leafs): N(size(leafs)), _meta(4 * N) {
build(leafs);
}
void pull(size_t v, size_t l, size_t r) {
if(r - l > 1) {
_meta[v].pull(_meta[2 * v], _meta[2 * v + 1], l, r);
}
}
void push(size_t v, size_t l, size_t r) {
if(r - l > 1) {
_meta[v].push(&_meta[2 * v], &_meta[2 * v + 1], l, r);
} else {
_meta[v].push(nullptr, nullptr, l, r);
}
}
void build(auto &a, size_t v, size_t l, size_t r) {
if(r - l == 1) {
if(l < size(a)) {
_meta[v] = a[l];
}
} else {
size_t m = std::midpoint(l, r);
build(a, 2 * v, l, m);
build(a, 2 * v + 1, m, r);
pull(v, l, r);
}
}
void build(auto &a) {
build(a, 1, 0, N);
}
void exec_on_segment(size_t a, size_t b, auto func, auto proceed, auto stop, size_t v, size_t l, size_t r) {
push(v, l, r);
if(r <= a || b <= l || stop(_meta[v])) {
return;
} else if(a <= l && r <= b && proceed(_meta[v])) {
func(_meta[v]);
push(v, l, r);
} else {
size_t m = std::midpoint(l, r);
exec_on_segment(a, b, func, proceed, stop, 2 * v, l, m);
exec_on_segment(a, b, func, proceed, stop, 2 * v + 1, m, r);
pull(v, l, r);
}
}
static constexpr auto default_true = [](auto const&){return true;};
static constexpr auto default_false = [](auto const&){return false;};
void exec_on_segment(size_t a, size_t b, auto func, auto proceed, auto stop) {
exec_on_segment(a, b, func, proceed, stop, 1, 0, N);
}
void exec_on_segment(size_t a, size_t b, auto func) {
exec_on_segment(a, b, func, default_true, default_false);
}
};
}
#endif // CP_ALGO_STRUCTURES_SEGMENT_TREE_HPP#line 1 "cp-algo/structures/segtree.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#include <iostream>
#include <forward_list>
// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif
namespace cp_algo {
template<typename T, size_t Align = 32>
class big_alloc {
static_assert(Align >= alignof(void*), "Align must be at least pointer-size");
static_assert(std::has_single_bit(Align), "Align must be a power of two");
public:
using value_type = T;
template<class U>
struct rebind {
using other = big_alloc<U, Align>;
};
constexpr bool operator==(const big_alloc&) const = default;
big_alloc() noexcept = default;
template<typename U, std::size_t A>
big_alloc(const big_alloc<U, A>&) noexcept {}
[[nodiscard]] T* allocate(std::size_t n) {
std::size_t padded = round_up(n * sizeof(T));
std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
if(padded >= MEGABYTE) {
void* raw = mmap(nullptr, padded, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
madvise(raw, padded, MADV_HUGEPAGE);
return static_cast<T*>(raw);
}
#endif
return static_cast<T*>(::operator new(padded, std::align_val_t(align)));
}
void deallocate(T* p, std::size_t n) noexcept {
if(!p) {
return;
}
std::size_t padded = round_up(n * sizeof(T));
std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
if(padded >= MEGABYTE) {
munmap(p, padded);
return;
}
#endif
::operator delete(p, padded, std::align_val_t(align));
}
private:
static constexpr std::size_t MEGABYTE = 1 << 20;
static constexpr std::size_t round_up(std::size_t x) noexcept {
return (x + Align - 1) / Align * Align;
}
};
template<typename T>
using big_vector = std::vector<T, big_alloc<T>>;
template<typename T>
using big_basic_string = std::basic_string<T, std::char_traits<T>, big_alloc<T>>;
template<typename T>
using big_deque = std::deque<T, big_alloc<T>>;
template<typename T>
using big_stack = std::stack<T, big_deque<T>>;
template<typename T>
using big_queue = std::queue<T, big_deque<T>>;
template<typename T>
using big_priority_queue = std::priority_queue<T, big_vector<T>>;
template<typename T>
using big_forward_list = std::forward_list<T, big_alloc<T>>;
using big_string = big_basic_string<char>;
template<typename Key, typename Value, typename Compare = std::less<Key>>
using big_map = std::map<Key, Value, Compare, big_alloc<std::pair<const Key, Value>>>;
template<typename T, typename Compare = std::less<T>>
using big_multiset = std::multiset<T, Compare, big_alloc<T>>;
template<typename T, typename Compare = std::less<T>>
using big_set = std::set<T, Compare, big_alloc<T>>;
}
#line 5 "cp-algo/structures/segtree.hpp"
#include <numeric>
namespace cp_algo::structures {
template<typename meta>
struct segtree_t {
const size_t N;
big_vector<meta> _meta;
segtree_t(size_t n): N(n), _meta(4 * N) {}
segtree_t(big_vector<meta> leafs): N(size(leafs)), _meta(4 * N) {
build(leafs);
}
void pull(size_t v, size_t l, size_t r) {
if(r - l > 1) {
_meta[v].pull(_meta[2 * v], _meta[2 * v + 1], l, r);
}
}
void push(size_t v, size_t l, size_t r) {
if(r - l > 1) {
_meta[v].push(&_meta[2 * v], &_meta[2 * v + 1], l, r);
} else {
_meta[v].push(nullptr, nullptr, l, r);
}
}
void build(auto &a, size_t v, size_t l, size_t r) {
if(r - l == 1) {
if(l < size(a)) {
_meta[v] = a[l];
}
} else {
size_t m = std::midpoint(l, r);
build(a, 2 * v, l, m);
build(a, 2 * v + 1, m, r);
pull(v, l, r);
}
}
void build(auto &a) {
build(a, 1, 0, N);
}
void exec_on_segment(size_t a, size_t b, auto func, auto proceed, auto stop, size_t v, size_t l, size_t r) {
push(v, l, r);
if(r <= a || b <= l || stop(_meta[v])) {
return;
} else if(a <= l && r <= b && proceed(_meta[v])) {
func(_meta[v]);
push(v, l, r);
} else {
size_t m = std::midpoint(l, r);
exec_on_segment(a, b, func, proceed, stop, 2 * v, l, m);
exec_on_segment(a, b, func, proceed, stop, 2 * v + 1, m, r);
pull(v, l, r);
}
}
static constexpr auto default_true = [](auto const&){return true;};
static constexpr auto default_false = [](auto const&){return false;};
void exec_on_segment(size_t a, size_t b, auto func, auto proceed, auto stop) {
exec_on_segment(a, b, func, proceed, stop, 1, 0, N);
}
void exec_on_segment(size_t a, size_t b, auto func) {
exec_on_segment(a, b, func, default_true, default_false);
}
};
}
#ifndef CP_ALGO_STRUCTURES_SEGMENT_TREE_HPP
#define CP_ALGO_STRUCTURES_SEGMENT_TREE_HPP
#include "../util/big_alloc.hpp"
#include <vector>
#include <numeric>
namespace cp_algo::structures{ template<typename meta> struct segtree_t{ const size_t N; big_vector<meta>_meta; segtree_t(size_t n):N(n),_meta(4*N){} segtree_t(big_vector<meta>leafs):N(size(leafs)),_meta(4*N){ build(leafs); } void pull(size_t v,size_t l,size_t r){ if(r-l>1){ _meta[v].pull(_meta[2*v],_meta[2*v+1],l,r); } } void push(size_t v,size_t l,size_t r){ if(r-l>1){ _meta[v].push(&_meta[2*v],&_meta[2*v+1],l,r); }else{ _meta[v].push(nullptr,nullptr,l,r); } } void build(auto&a,size_t v,size_t l,size_t r){ if(r-l==1){ if(l<size(a)){ _meta[v] =a[l]; } }else{ size_t m=std::midpoint(l,r); build(a,2*v,l,m); build(a,2*v+1,m,r); pull(v,l,r); } } void build(auto&a){ build(a,1,0,N); } void exec_on_segment(size_t a,size_t b,auto func,auto proceed,auto stop,size_t v,size_t l,size_t r){ push(v,l,r); if(r<=a||b<=l||stop(_meta[v])){ return; }else if(a<=l&&r<=b&&proceed(_meta[v])){ func(_meta[v]); push(v,l,r); }else{ size_t m=std::midpoint(l,r); exec_on_segment(a,b,func,proceed,stop,2*v,l,m); exec_on_segment(a,b,func,proceed,stop,2*v+1,m,r); pull(v,l,r); } } static constexpr auto default_true= [](auto const&){return true;}; static constexpr auto default_false= [](auto const&){return false;}; void exec_on_segment(size_t a,size_t b,auto func,auto proceed,auto stop){ exec_on_segment(a,b,func,proceed,stop,1,0,N); } void exec_on_segment(size_t a,size_t b,auto func){ exec_on_segment(a,b,func,default_true,default_false); } }; }
#endif
#line 1 "cp-algo/structures/segtree.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#include <iostream>
#include <forward_list>
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif
namespace cp_algo{ template<typename T,size_t Align=32> class big_alloc{ static_assert(Align>=alignof(void*),"Align must be at least pointer-size"); static_assert(std::has_single_bit(Align),"Align must be a power of two"); public: using value_type=T; template<class U> struct rebind{ using other=big_alloc<U,Align>; }; constexpr bool operator==(const big_alloc&)const=default; big_alloc()noexcept=default; template<typename U,std::size_t A> big_alloc(const big_alloc<U,A>&)noexcept{} [[nodiscard]]T*allocate(std::size_t n){ std::size_t padded=round_up(n*sizeof(T)); std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){ void*raw=mmap(nullptr,padded,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0); madvise(raw,padded,MADV_HUGEPAGE); return static_cast<T*>(raw); }
#endif
return static_cast<T*>(::operator new(padded,std::align_val_t(align))); } void deallocate(T*p,std::size_t n)noexcept{ if(!p){ return; } std::size_t padded=round_up(n*sizeof(T)); std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){ munmap(p,padded); return; }
#endif
::operator delete(p,padded,std::align_val_t(align)); } private: static constexpr std::size_t MEGABYTE=1<<20; static constexpr std::size_t round_up(std::size_t x)noexcept{ return(x+Align-1)/Align*Align; } }; template<typename T> using big_vector=std::vector<T,big_alloc<T>>; template<typename T> using big_basic_string=std::basic_string<T,std::char_traits<T>,big_alloc<T>>; template<typename T> using big_deque=std::deque<T,big_alloc<T>>; template<typename T> using big_stack=std::stack<T,big_deque<T>>; template<typename T> using big_queue=std::queue<T,big_deque<T>>; template<typename T> using big_priority_queue=std::priority_queue<T,big_vector<T>>; template<typename T> using big_forward_list=std::forward_list<T,big_alloc<T>>; using big_string=big_basic_string<char>; template<typename Key,typename Value,typename Compare=std::less<Key>> using big_map=std::map<Key,Value,Compare,big_alloc<std::pair<const Key,Value>>>; template<typename T,typename Compare=std::less<T>> using big_multiset=std::multiset<T,Compare,big_alloc<T>>; template<typename T,typename Compare=std::less<T>> using big_set=std::set<T,Compare,big_alloc<T>>; }
#line 5 "cp-algo/structures/segtree.hpp"
#include <numeric>
namespace cp_algo::structures{ template<typename meta> struct segtree_t{ const size_t N; big_vector<meta>_meta; segtree_t(size_t n):N(n),_meta(4*N){} segtree_t(big_vector<meta>leafs):N(size(leafs)),_meta(4*N){ build(leafs); } void pull(size_t v,size_t l,size_t r){ if(r-l>1){ _meta[v].pull(_meta[2*v],_meta[2*v+1],l,r); } } void push(size_t v,size_t l,size_t r){ if(r-l>1){ _meta[v].push(&_meta[2*v],&_meta[2*v+1],l,r); }else{ _meta[v].push(nullptr,nullptr,l,r); } } void build(auto&a,size_t v,size_t l,size_t r){ if(r-l==1){ if(l<size(a)){ _meta[v] =a[l]; } }else{ size_t m=std::midpoint(l,r); build(a,2*v,l,m); build(a,2*v+1,m,r); pull(v,l,r); } } void build(auto&a){ build(a,1,0,N); } void exec_on_segment(size_t a,size_t b,auto func,auto proceed,auto stop,size_t v,size_t l,size_t r){ push(v,l,r); if(r<=a||b<=l||stop(_meta[v])){ return; }else if(a<=l&&r<=b&&proceed(_meta[v])){ func(_meta[v]); push(v,l,r); }else{ size_t m=std::midpoint(l,r); exec_on_segment(a,b,func,proceed,stop,2*v,l,m); exec_on_segment(a,b,func,proceed,stop,2*v+1,m,r); pull(v,l,r); } } static constexpr auto default_true= [](auto const&){return true;}; static constexpr auto default_false= [](auto const&){return false;}; void exec_on_segment(size_t a,size_t b,auto func,auto proceed,auto stop){ exec_on_segment(a,b,func,proceed,stop,1,0,N); } void exec_on_segment(size_t a,size_t b,auto func){ exec_on_segment(a,b,func,default_true,default_false); } }; }