C++树状数组模板库

C++树状数组模板库（BITree.hpp）

更新日志

2022.3.15更新2022.3.11更新2022.3.8更新 模板库源码（C++14标准）

基本完成了模板库并发布到CSDN博客；

完成了部分内容；

完成了部分内容；

#ifndef BITREE_HPP
#define BITREE_HPP

#include "QuickIO.hpp"
#include 
#include 

namespace algo
{
    using qio::Size;

    template 
    using DynArray = std::vector;
    template 
    using InitializerList = std::initializer_list;
    struct Plus
    {
        struct Inverse
        {
            template 
            Res operator()(const S &a, const T &b)
            {
                return (a - b);
            }
            template 
            static Res calc(const S &a, const T &b)
            {
                return (a - b);
            }
        };

        template 
        static constexpr T initial()
        {
            return T();
        }
        template 
        Res operator()(const S &a, const T &b)
        {
            return (a + b);
        }
        template 
        static Res calc(const S &a, const T &b)
        {
            return (a + b);
        }
    };
    struct Multiply
    {
        struct Inverse
        {
            template 
            Res operator()(const S &a, const T &b)
            {
                return (a / b);
            }
            template 
            static Res calc(const S &a, const T &b)
            {
                return (a / b);
            }
        };

        template 
        constexpr T initial()
        {
            return 1;
        }
        template 
        Res operator()(const S &a, const T &b)
        {
            return (a * b);
        }
        template 
        static Res calc(const S &a, const T &b)
        {
            return (a * b);
        }
    };
    template 
    class BITree
    {
    public:
        using Seq = DynArray;
        using Iterator = typename Seq::iterator;
        using ConstIterator = typename Seq::const_iterator;
        using ReverseIter = typename Seq::reverse_iterator;
        using ConstReverseIter = typename Seq::const_reverse_iterator;

    protected:
        Seq bitree;

        inline static Size lowbit(Size x)
        {
            return (x & -x);
        }

    public:
        BITree() = default;
        BITree(const Seq &seq, bool isBITree = false)
            : bitree(seq)
        {
            if (!isBITree)
            {
                CombineFunc f;
                for (Size i = 0, j, len = seq.size(); i ^ len; ++i)
                {
                    if ((j = i + lowbit(i + 1)) < len)
                    {
                        this->bitree.at(j) =
                            f.template operator()(this->bitree.at(j),
                                                           this->bitree.at(i));
                    }
                }
            }
        }
        BITree(Size initialSize)
            : bitree(initialSize,
                     CombineFunc::template initial()) {}
        template 
        BITree(ForwardIterator pBegin, ForwardIterator pEnd)
        {
            auto dist = std::distance(pBegin, pEnd);
            CombineFunc f;
            if (dist > 0)
            {
                Size len = dist;
                this->bitree.resize(len);
                for (Size i = 0; i ^ len; ++i)
                {
                    this->bitree.at(i) = f.template initial();
                }
                for (Size i = 0, j; i ^ len; ++i)
                {
                    this->bitree.at(i) = *(pBegin++);
                    if ((j = i + lowbit(i + 1)) < this->bitree.size())
                    {
                        this->bitree.at(j) =
                            f.template operator()(this->bitree.at(j),
                                                           this->bitree.at(i));
                    }
                }
            }
        }

        inline Size size() const { return this->bitree.size(); }
        inline void resize(Size newSize)
        {
            CombineFunc f;
            Size i = this->bitree.size() + 1;
            this->bitree.resize(newSize);
            for (Size j; i <= newSize; ++i)
            {
                this->bitree.at(i - 1) =
                    (((j = i - this->lowbit(i) + 1) < i)
                         ? f.template operator()(this->sum(j, i - 1),
                                                          f.template initial())
                         : f.template initial());
            }
        }

        inline const T *data() const { return this->bitree.data(); }

        template 
        inline Res sum(Size iEnd) const
        {
            CombineFunc f;
            Res res = f.template initial();
            for (; iEnd; iEnd -= this->lowbit(iEnd))
            {
                res = f.template operator()(res, this->bitree.at(iEnd - 1));
            }
            return res;
        }
        template 
        inline Res sum(Size iBegin, Size iEnd) const
        {
            return CombineFunc::Inverse::template calc(this->sum(iEnd), this->sum(iBegin));
        }
        inline T at(Size index) const { return this->bitree.sum(index, index + 1); }
        inline T at(Size iBegin, Size iEnd) const { return this->sum(iBegin, iEnd); }
        inline T operator[](Size index) const
        {
            return this->sum(index, index + 1);
        }

        template 
        inline void modify(Size index, const S &variation)
        {
            CombineFunc f;
            for (Size i = index + 1; i <= this->bitree.size(); i += this->lowbit(i))
            {
                this->bitree.at(i - 1) =
                    f.template operator()(this->bitree.at(i - 1), variation);
            }
        }

        inline ConstIterator begin() const { return this->bitree.begin(); }
        inline ConstIterator cbegin() const { return this->bitree.cbegin(); }
        inline ConstReverseIter rbegin() const { return this->bitree.rbegin(); }
        inline ConstReverseIter crbegin() const { return this->bitree.crbegin(); }
        inline ConstIterator end() const { return this->bitree.end(); }
        inline ConstIterator cend() const { return this->bitree.cend(); }
        inline ReverseIter rend() { return this->bitree.rend(); }
        inline ConstReverseIter rend() const { return this->bitree.rend(); }
        inline ConstReverseIter crend() const { return this->bitree.crend(); }

    private:
    };
}

#endif