SegTree with Eigen

#include <iostream>
#include <vector>
#include <algorithm>
#include <Eigen/Dense>

using namespace Eigen;
using ll = long long;

template <class T>
class SegmentTree
{
private:

    struct Node
    {
        T modify;
        T query;
    };

    int size;
    T q_neutral;
    T m_neutral;
    T(*query)(const T&, const T&);
    T(*modify)(const T&, const T&);
    std::vector<Node> tree;

    void build(const std::vector<T>& a, int v, int left, int right)
    {
        if (left + 1 == right)
            tree[v].query = a[left];
        else
        {
            int mid = (left + right) >> 1;
            build(a, 2 * v, left, mid);
            build(a, 2 * v + 1, mid, right);
            tree[v].query = query(tree[2 * v].query, tree[2 * v + 1].query);
        }
    }

    void propagate(int v, int left, int right)
    {
        if (left + 1 == right || tree[v].modify == m_neutral) return;

        tree[2 * v].modify = modify(tree[2 * v].modify, tree[v].modify);
        tree[2 * v].query = modify(tree[2 * v].query, tree[v].modify);
        tree[2 * v + 1].modify = modify(tree[2 * v + 1].modify, tree[v].modify);
        tree[2 * v + 1].query = modify(tree[2 * v + 1].query, tree[v].modify);

        tree[v].modify = m_neutral;
    }


    T getQuery(int v, int start, int end, int left, int right)
    {
        propagate(v, left, right);
        if (end <= left || right <= start)
            return q_neutral;
        if (start <= left && right <= end)
            return tree[v].query;
        else
        {
            int mid = (left + right) >> 1;
            return query(getQuery(2 * v, start, end, left, mid),
                getQuery(2 * v + 1, start, end, mid, right));
        }
    }

    void update(int v, const T& x, int start, int end, int left, int right)
    {
        propagate(v, left, right);
        if (end <= left || right <= start)
            return;
        if (start <= left && right <= end)
        {
            tree[v].modify = modify(tree[v].modify, x);
            tree[v].query = modify(tree[v].query, x);
            return;
        }
        else
        {
            int mid = (left + right) >> 1;
            update(2 * v, x, start, end, left, mid);
            update(2 * v + 1, x, start, end, mid, right);
            tree[v].query = query(tree[2 * v].query, tree[2 * v + 1].query);
        }

    }

    void get_init_vec_help(std::vector<T>& vec, int v, int left, int right)
    {
        if (left + 1 == right)
            vec[left] = tree[v].query;
        else
        {
            int mid = (left + right) >> 1;

            get_init_vec_help(vec, 2 * v, left, mid);
            get_init_vec_help(vec, 2 * v + 1, mid, right);
        }
    }

    void full_propagate(int v, int left, int right)
    {
        if (left + 1 == right) return;

        propagate(v, left, right);

        int mid = (left + right) >> 1;
        full_propagate(2 * v, left, mid);
        full_propagate(2 * v + 1, mid, right);
    }

public:


    SegmentTree(int n, T(*_query)(const T&, const T&), T(*_modify)(const T&, const T&), const T& _q_neutral = T(), const T& _m_neutral = T())
        : size(n)
        , q_neutral(_q_neutral)
        , m_neutral(_m_neutral)
        , query(_query)
        , modify(_modify)
        , tree(n << 2, { m_neutral , q_neutral })
    {
        if (!_query || !_modify) throw "Nullptr";
    }

    SegmentTree(const std::vector<T>& vec, T(*_query)(const T&, const T&), T(*_modify)(const T&, const T&), const T& _q_neutral = T(), const T& _m_neutral = T())
        : SegmentTree(vec.size(), _query, _modify, _q_neutral, _m_neutral)
    {
        if (!_query || !_modify) throw "Nullptr";
        build(vec, 1, 0, size);
    }

    SegmentTree<T> operator =(const SegmentTree<T>& Tree)
    {
        if (this == Tree) return *this;

        size = Tree.size;
        tree = Tree.tree;
        q_neutral = Tree.q_neutral;
        m_neutral = Tree.m_neutral;
        modify = Tree.modify;
        query = Tree.query;

        return *this;
    }

    SegmentTree<T> merge(SegmentTree<T>& Tree)
    {
        if (q_neutral != Tree.q_neutral || m_neutral != Tree.m_neutral) return *this;

        Tree.full_propagate(1, 0, Tree.size);
        full_propagate(1, 0, size);

        std::vector<T> init_vec = get_init_vec();
        std::vector<T> Tree_init_vec = Tree.get_init_vec();

        init_vec.insert(init_vec.end(), Tree_init_vec.begin(), Tree_init_vec.end());
        SegmentTree<T> rez(init_vec, query, modify, q_neutral, m_neutral);

        return rez;
    }

    void update(int start, int end, const T& x)
    {
        update(1, x, start, end + 1, 0, size);
    }

    T getQuery(int start, int end)
    {
        return getQuery(1, start, end + 1, 0, size);
    }

    T getQueryNeutral() const
    {
        return q_neutral;
    }

    T getModifyNeutral() const
    {
        return m_neutral;
    }

    std::vector<T> get_init_vec()
    {
        std::vector<T> result(size, T());
        get_init_vec_help(result, 1, 0, size);

        return result;
    }

    template <class T>
    friend std::ostream& operator << (std::ostream& out, const SegmentTree<T>& Tree);
};

template <class T>
std::ostream& operator << (std::ostream& out, const SegmentTree<T>& Tree)
{
    if (out)
    {
        for (auto it : Tree.tree)
        {
            std::cout << it.query << " " << it.modify << '\n';
        }
    }

    return out;
}

template <class T>
T modify_mat(const T& a, const T& b)
{
    MatrixXi maxtrix_sum_neutral(2, 2);
    maxtrix_sum_neutral.setZero();

    if (b == maxtrix_sum_neutral) return a;
    return b;
}

template <class T>
T query(const T& a, const T& b)
{
    return a + b;
}

template <class T>
T multiply(const T& a, const T& b)
{
    return a * b;
}


int main()
{
    setlocale(LC_ALL, "Russian");
    /*std::vector<ll> vec = { 2,3,4,1,5,6 };

    ll(*ptr_modify_vec)(const ll&, const ll&) = &multiply;
    ll(*ptr_query_vec)(const ll&, const ll&) = &query;

    SegmentTree<ll> tree_vec(vec, ptr_query_vec, ptr_modify_vec, 0, 1);

    std::cout << "Сумма всего отрезка: " << tree_vec.getQuery(0, 5) << '\n';
    tree_vec.update(0, 5, 2);
    std::cout << "Сумма всего отрезка после умножения всего отрезка на 2: " << tree_vec.getQuery(0, 5) << '\n';


    std::cout << "\n////////////////////////////////////////////////////////\n";*/

    //Проверим работу ДО на матрицах 2х2
    MatrixXi m1(2, 2), m2(2,2), m3(2,2), m4(2,2);
    m1 << 1, 0, 0, 1;
    m2 << 2, 2, 2, 2;
    m3 << 3, 3, 3, 3;
    m4 << 1, 3, 2, 3;

    MatrixXi maxtrix_sum_neutral(2, 2);
    maxtrix_sum_neutral.setZero();

    std::vector<MatrixXi> vec_mat = { m1,m2,m3,m4 };

    MatrixXi(*ptr_modify)(const MatrixXi&, const MatrixXi&) = &modify_mat;
    MatrixXi(*ptr_query)(const MatrixXi&, const MatrixXi&) = &query;
    MatrixXi(*ptr_mult)(const MatrixXi&, const MatrixXi&) = &multiply;

    SegmentTree<MatrixXi> tree(vec_mat, ptr_query, ptr_modify, maxtrix_sum_neutral, maxtrix_sum_neutral);
    std::vector<MatrixXi> init = tree.get_init_vec();


    //std::cout <<"Четыре матрицы 2х2 для проверки работы ДО на объектах сложной структруы:\n"
        //<< m1 << "\n\n" << m2 << "\n\n" << m3 << "\n\n" << m4 << '\n';


    //std::cout << "Сумма всех четырех матриц:\n" << tree.getQuery(0,3) << '\n';


    //std::cout << "\n////////////////////////////////////////////////////////\n";

    std::vector<MatrixXi> matrices(19); //Вектор на котором будем строить дерево отрезков

    MatrixXi MULT_NEUTRAL(6, 6), SUM_NEUTRAL(6, 6);
    MULT_NEUTRAL.setIdentity();
    SUM_NEUTRAL.setZero();

    // Заполнение каждой матрицы случайными значениями
    for (int i = 0; i < matrices.size(); i++)
        matrices[i] = MatrixXi::Random(6, 6);

    SegmentTree<MatrixXi> tree2(matrices, ptr_query, ptr_mult, SUM_NEUTRAL, MULT_NEUTRAL);
    std::vector<MatrixXi> init_vec = tree2.get_init_vec();
    MatrixXi all_sum = tree2.getQuery(0, 18);

    //Проверка корректности операции запроса
    std::cout << "Проверяем верно ли выполняется запрос на сумму матриц: " << (tree2.getQuery(0, 1) == (init_vec[0] + init_vec[1])) << '\n';

    //Умножим первые четыре элемента на нулевую матрицу и проверим, что отложенные операции работают

    tree2.update(0, 3, SUM_NEUTRAL);

    for (int i = 0; i < 4; ++i)
        all_sum = all_sum - init_vec[i];

    MatrixXi all_sum_new = tree2.getQuery(0, 18);

    std::cout << "Проверяем верно ли работают отложенные операции: " << (all_sum_new == all_sum) << '\n';

    return 0;
}