cp-algo/structures/fenwick.hpp

• View this file on GitHub
• Last update: 2026-10-16 14:16:08+02:00
• Include: #include "cp-algo/structures/fenwick.hpp"

Depends on

• cp-algo/util/big_alloc.hpp

Required by

• cp-algo/structures/fenwick_set.hpp

Verified with

• Longest Increasing Subsequence (verify/structures/fenwick/lis.test.cpp)
• Ordered Set (verify/structures/fenwick/ordered_set.test.cpp)
• Point Add Range Sum (verify/structures/fenwick/point_add_range_sum.test.cpp)

Code

#ifndef CP_ALGO_STRUCTURES_FENWICK_HPP
#define CP_ALGO_STRUCTURES_FENWICK_HPP
#include "../util/big_alloc.hpp"
#include <cassert>
#include <vector>
namespace cp_algo::structures {
    template <typename Op>
    struct inverse_op {};

    template <typename T>
    struct inverse_op<std::plus<T>> {
        static T apply(T const& a, T const& b) {
            return a - b;
        }
    };

    template <typename T>
    struct inverse_op<std::multiplies<T>> {
        static T apply(T const& a, T const& b) {
            return a / b;
        }
    };

    template<typename T, std::ranges::range Container = big_vector<T>, typename Op = std::plus<T>>
    struct fenwick {
        Op op;
        size_t n;
        Container data;

        fenwick(auto &&range, Op &&op = Op{}): op(std::move(op)) {
            assign(std::move(range));
        }
        void to_prefix_folds() {
            for(size_t i = 1; i < n; i++) {
                if(i + (i & -i) <= n) {
                    data[i + (i & -i)] = op(data[i + (i & -i)], data[i]);
                }
            }
        }
        void assign(auto &&range) {
            n = size(range) - 1;
            data = std::move(range);
            to_prefix_folds();
        }
        void update(size_t x, T const& v) {
            for(++x; x <= n; x += x & -x) {
                data[x] = op(data[x], v);
            }
        }
        // fold of [0, r)
        T prefix_fold(size_t r) const {
            assert(r <= n);
            T res = {};
            for(; r; r -= r & -r) {
                res = op(res, data[r]);
            }
            return res;
        }
        // fold of [l, r)
        T range_fold(size_t l, size_t r) const {
            return inverse_op<Op>::apply(prefix_fold(r), prefix_fold(l));
        }
        // Last x s.t. prefix_fold(x) <= k
        // Assumes prefix_fold is monotonic
        // returns [x, prefix_fold(x)]
        auto prefix_lower_bound(T k) const {
            size_t x = 0;
            T pref = {};
            for(size_t i = std::bit_floor(n); i; i /= 2) {
                if(x + i <= n && op(pref, data[x + i]) <= k) {
                    pref = op(pref, data[x + i]);
                    x += i;
                }
            }
            return std::pair{x, pref};
        }
    };

    template<std::ranges::range Container, typename Op>
    fenwick(Container&&, Op&&) -> fenwick<std::ranges::range_value_t<Container>, Container, Op>;
    template<std::ranges::range Container>
    fenwick(Container&&) -> fenwick<std::ranges::range_value_t<Container>, Container>;

    auto maxer = [](auto const& a, auto const& b) {
        return std::max(a, b);
    };
    template<typename T, std::ranges::range Container = big_vector<T>>
    struct fenwick_max: fenwick<T, Container, decltype(maxer)> {
        using fenwick<T, Container, decltype(maxer)>::fenwick;
    };
    template<std::ranges::range Container>
    fenwick_max(Container&&) -> fenwick_max<std::ranges::range_value_t<Container>, Container>;

}
#endif // CP_ALGO_STRUCTURES_FENWICK_HPP

#line 1 "cp-algo/structures/fenwick.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 4 "cp-algo/structures/fenwick.hpp"
#include <cassert>
#line 6 "cp-algo/structures/fenwick.hpp"
namespace cp_algo::structures {
    template <typename Op>
    struct inverse_op {};

    template <typename T>
    struct inverse_op<std::plus<T>> {
        static T apply(T const& a, T const& b) {
            return a - b;
        }
    };

    template <typename T>
    struct inverse_op<std::multiplies<T>> {
        static T apply(T const& a, T const& b) {
            return a / b;
        }
    };

    template<typename T, std::ranges::range Container = big_vector<T>, typename Op = std::plus<T>>
    struct fenwick {
        Op op;
        size_t n;
        Container data;

        fenwick(auto &&range, Op &&op = Op{}): op(std::move(op)) {
            assign(std::move(range));
        }
        void to_prefix_folds() {
            for(size_t i = 1; i < n; i++) {
                if(i + (i & -i) <= n) {
                    data[i + (i & -i)] = op(data[i + (i & -i)], data[i]);
                }
            }
        }
        void assign(auto &&range) {
            n = size(range) - 1;
            data = std::move(range);
            to_prefix_folds();
        }
        void update(size_t x, T const& v) {
            for(++x; x <= n; x += x & -x) {
                data[x] = op(data[x], v);
            }
        }
        // fold of [0, r)
        T prefix_fold(size_t r) const {
            assert(r <= n);
            T res = {};
            for(; r; r -= r & -r) {
                res = op(res, data[r]);
            }
            return res;
        }
        // fold of [l, r)
        T range_fold(size_t l, size_t r) const {
            return inverse_op<Op>::apply(prefix_fold(r), prefix_fold(l));
        }
        // Last x s.t. prefix_fold(x) <= k
        // Assumes prefix_fold is monotonic
        // returns [x, prefix_fold(x)]
        auto prefix_lower_bound(T k) const {
            size_t x = 0;
            T pref = {};
            for(size_t i = std::bit_floor(n); i; i /= 2) {
                if(x + i <= n && op(pref, data[x + i]) <= k) {
                    pref = op(pref, data[x + i]);
                    x += i;
                }
            }
            return std::pair{x, pref};
        }
    };

    template<std::ranges::range Container, typename Op>
    fenwick(Container&&, Op&&) -> fenwick<std::ranges::range_value_t<Container>, Container, Op>;
    template<std::ranges::range Container>
    fenwick(Container&&) -> fenwick<std::ranges::range_value_t<Container>, Container>;

    auto maxer = [](auto const& a, auto const& b) {
        return std::max(a, b);
    };
    template<typename T, std::ranges::range Container = big_vector<T>>
    struct fenwick_max: fenwick<T, Container, decltype(maxer)> {
        using fenwick<T, Container, decltype(maxer)>::fenwick;
    };
    template<std::ranges::range Container>
    fenwick_max(Container&&) -> fenwick_max<std::ranges::range_value_t<Container>, Container>;

}

#ifndef CP_ALGO_STRUCTURES_FENWICK_HPP
#define CP_ALGO_STRUCTURES_FENWICK_HPP
#include "../util/big_alloc.hpp"
#include <cassert>
#include <vector>
namespace cp_algo::structures{ template<typename Op> struct inverse_op{}; template<typename T> struct inverse_op<std::plus<T>>{ static T apply(T const&a,T const&b){ return a-b; } }; template<typename T> struct inverse_op<std::multiplies<T>>{ static T apply(T const&a,T const&b){ return a/b; } }; template<typename T,std::ranges::range Container=big_vector<T>,typename Op=std::plus<T>> struct fenwick{ Op op; size_t n; Container data; fenwick(auto&&range,Op&&op=Op{}):op(std::move(op)){ assign(std::move(range)); } void to_prefix_folds(){ for(size_t i=1;i<n;i++){ if(i+(i& -i)<=n){ data[i+(i& -i)] =op(data[i+(i& -i)],data[i]); } } } void assign(auto&&range){ n=size(range)-1; data=std::move(range); to_prefix_folds(); } void update(size_t x,T const&v){ for(++x;x<=n;x+=x& -x){ data[x] =op(data[x],v); } } T prefix_fold(size_t r)const{ assert(r<=n); T res={}; for(;r;r-=r& -r){ res=op(res,data[r]); } return res; } T range_fold(size_t l,size_t r)const{ return inverse_op<Op>::apply(prefix_fold(r),prefix_fold(l)); } auto prefix_lower_bound(T k)const{ size_t x=0; T pref={}; for(size_t i=std::bit_floor(n);i;i/=2){ if(x+i<=n&&op(pref,data[x+i])<=k){ pref=op(pref,data[x+i]); x+=i; } } return std::pair{x,pref}; } }; template<std::ranges::range Container,typename Op> fenwick(Container&&,Op&&)->fenwick<std::ranges::range_value_t<Container>,Container,Op>; template<std::ranges::range Container> fenwick(Container&&)->fenwick<std::ranges::range_value_t<Container>,Container>; auto maxer= [](auto const&a,auto const&b){ return std::max(a,b); }; template<typename T,std::ranges::range Container=big_vector<T>> struct fenwick_max:fenwick<T,Container,decltype(maxer)>{ using fenwick<T,Container,decltype(maxer)>::fenwick; }; template<std::ranges::range Container> fenwick_max(Container&&)->fenwick_max<std::ranges::range_value_t<Container>,Container>; }
#endif

#line 1 "cp-algo/structures/fenwick.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 4 "cp-algo/structures/fenwick.hpp"
#include <cassert>
#line 6 "cp-algo/structures/fenwick.hpp"
namespace cp_algo::structures{ template<typename Op> struct inverse_op{}; template<typename T> struct inverse_op<std::plus<T>>{ static T apply(T const&a,T const&b){ return a-b; } }; template<typename T> struct inverse_op<std::multiplies<T>>{ static T apply(T const&a,T const&b){ return a/b; } }; template<typename T,std::ranges::range Container=big_vector<T>,typename Op=std::plus<T>> struct fenwick{ Op op; size_t n; Container data; fenwick(auto&&range,Op&&op=Op{}):op(std::move(op)){ assign(std::move(range)); } void to_prefix_folds(){ for(size_t i=1;i<n;i++){ if(i+(i& -i)<=n){ data[i+(i& -i)] =op(data[i+(i& -i)],data[i]); } } } void assign(auto&&range){ n=size(range)-1; data=std::move(range); to_prefix_folds(); } void update(size_t x,T const&v){ for(++x;x<=n;x+=x& -x){ data[x] =op(data[x],v); } } T prefix_fold(size_t r)const{ assert(r<=n); T res={}; for(;r;r-=r& -r){ res=op(res,data[r]); } return res; } T range_fold(size_t l,size_t r)const{ return inverse_op<Op>::apply(prefix_fold(r),prefix_fold(l)); } auto prefix_lower_bound(T k)const{ size_t x=0; T pref={}; for(size_t i=std::bit_floor(n);i;i/=2){ if(x+i<=n&&op(pref,data[x+i])<=k){ pref=op(pref,data[x+i]); x+=i; } } return std::pair{x,pref}; } }; template<std::ranges::range Container,typename Op> fenwick(Container&&,Op&&)->fenwick<std::ranges::range_value_t<Container>,Container,Op>; template<std::ranges::range Container> fenwick(Container&&)->fenwick<std::ranges::range_value_t<Container>,Container>; auto maxer= [](auto const&a,auto const&b){ return std::max(a,b); }; template<typename T,std::ranges::range Container=big_vector<T>> struct fenwick_max:fenwick<T,Container,decltype(maxer)>{ using fenwick<T,Container,decltype(maxer)>::fenwick; }; template<std::ranges::range Container> fenwick_max(Container&&)->fenwick_max<std::ranges::range_value_t<Container>,Container>; }

Back to top page