[C++知识库]C++树状数组模板库

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

更新日志

2022.3.15更新

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

2022.3.11更新

1. 完成了部分内容；

2022.3.8更新

1. 完成了部分内容；

模板库源码（C++14标准）

#ifndef BITREE_HPP
#define BITREE_HPP

#include "QuickIO.hpp"
#include <initializer_list>
#include <vector>

namespace algo
{
    using qio::Size;

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

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

        template <typename T>
        constexpr T initial()
        {
            return 1;
        }
        template <typename S, typename T = S, typename Res>
        Res operator()(const S &a, const T &b)
        {
            return (a * b);
        }
        template <typename S, typename T = S, typename Res>
        static Res calc(const S &a, const T &b)
        {
            return (a * b);
        }
    };
    template <typename T, typename CombineFunc = Plus>
    class BITree
    {
    public:
        using Seq = DynArray<T>;
        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()<T, T, T>(this->bitree.at(j),
                                                           this->bitree.at(i));
                    }
                }
            }
        }
        BITree(Size initialSize)
            : bitree(initialSize,
                     CombineFunc::template initial<T>()) {}
        template <typename ForwardIterator>
        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<T>();
                }
                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()<T, T, T>(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()<T, T, T>(this->sum(j, i - 1),
                                                          f.template initial<T>())
                         : f.template initial<T>());
            }
        }

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

        template <typename Res = T>
        inline Res sum(Size iEnd) const
        {
            CombineFunc f;
            Res res = f.template initial<Res>();
            for (; iEnd; iEnd -= this->lowbit(iEnd))
            {
                res = f.template operator()<Res, T, Res>(res, this->bitree.at(iEnd - 1));
            }
            return res;
        }
        template <typename Res = T>
        inline Res sum(Size iBegin, Size iEnd) const
        {
            return CombineFunc::Inverse::template calc<Res, Res, Res>(this->sum<Res>(iEnd), this->sum<Res>(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 <typename S>
        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()<T, S, T>(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