DisjointSparseTable
(lib/13-static-range-query/DisjointSparseTable.cpp)

• View this file on GitHub
• Last update: 2023-05-30 05:01:32+09:00

Verified with

• test/static-range-query/DisjointSparseTable.test.cpp

Code

/*
 * @title DisjointSparseTable
 * @docs md/static-range-query/DisjointSparseTable.md
 */
template<class Operator> class DisjointSparseTable{
public:
    using TypeNode = typename Operator::TypeNode;
    size_t depth;
    size_t length;
    vector<TypeNode> node;
    vector<size_t> msb;

    DisjointSparseTable(const vector<TypeNode>& vec) {
        for(depth = 0;(1<<depth)<=vec.size();++depth);
        length = (1<<depth);

        //msb
        msb.resize(length,0);
        for(int i = 0; i < length; ++i) for(int j = 0; j < depth; ++j) if(i>>j) msb[i] = j;

        //init value
        node.resize(depth*length,Operator::unit_node);
        for(int i = 0; i < vec.size(); ++i) node[i] = vec[i];

        for(int i = 1; i < depth; ++i) {
            for(int r = (1<<i),l = r-1; r < length; r += (2<<i),l = r-1){
                //init accumulate
                node[i*length+l] = node[l];
                node[i*length+r] = node[r];
                //accumulate
                for(int k = 1; k < (1<<i); ++k) {
                    node[i*length+l-k] = Operator::func_fold(node[i*length+l-k+1],node[l-k]);
                    node[i*length+r+k] = Operator::func_fold(node[i*length+r+k-1],node[r+k]);
                }
            }
        }
    }

    //[l,r)
    TypeNode fold(int l,int r) {
        r--;
        return (l>r||l<0||length<=r) ? Operator::unit_node: (l==r ? node[l] : Operator::func_fold(node[msb[l^r]*length+l],node[msb[l^r]*length+r]));
    }
};

//sum
template<class T> struct NodeSum {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
};

#line 1 "lib/13-static-range-query/DisjointSparseTable.cpp"
/*
 * @title DisjointSparseTable
 * @docs md/static-range-query/DisjointSparseTable.md
 */
template<class Operator> class DisjointSparseTable{
public:
    using TypeNode = typename Operator::TypeNode;
    size_t depth;
    size_t length;
    vector<TypeNode> node;
    vector<size_t> msb;

    DisjointSparseTable(const vector<TypeNode>& vec) {
        for(depth = 0;(1<<depth)<=vec.size();++depth);
        length = (1<<depth);

        //msb
        msb.resize(length,0);
        for(int i = 0; i < length; ++i) for(int j = 0; j < depth; ++j) if(i>>j) msb[i] = j;

        //init value
        node.resize(depth*length,Operator::unit_node);
        for(int i = 0; i < vec.size(); ++i) node[i] = vec[i];

        for(int i = 1; i < depth; ++i) {
            for(int r = (1<<i),l = r-1; r < length; r += (2<<i),l = r-1){
                //init accumulate
                node[i*length+l] = node[l];
                node[i*length+r] = node[r];
                //accumulate
                for(int k = 1; k < (1<<i); ++k) {
                    node[i*length+l-k] = Operator::func_fold(node[i*length+l-k+1],node[l-k]);
                    node[i*length+r+k] = Operator::func_fold(node[i*length+r+k-1],node[r+k]);
                }
            }
        }
    }

    //[l,r)
    TypeNode fold(int l,int r) {
        r--;
        return (l>r||l<0||length<=r) ? Operator::unit_node: (l==r ? node[l] : Operator::func_fold(node[msb[l^r]*length+l],node[msb[l^r]*length+r]));
    }
};

//sum
template<class T> struct NodeSum {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
};

Back to top page