Нахождение НВП при помощи дерева отрезков

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
 
auto max_comp = [](const std::tuple<int, int, int, int> &fst, const std::tuple<int, int, int, int> &snd) {
    return (std::get<2>(fst) < std::get<2>(snd));
};
 
 
struct SegTree {
    int lb, rb;
 
    // Изначально в предке -1 можем хранить, т.к. все равно введенные числа не дойдут до этого диапазона
    std::tuple<int, int, int, int> max_ind_elem_di_pred_ind = {-1, -1, 0, -1};
    // Индекс элемента, на который оканчивается возр. последовательность, сам элемент, динамика d[i] и предок
 
    SegTree *l_child = nullptr, *r_child = nullptr;
 
    SegTree(int lb_, int rb_) : lb(lb_), rb(rb_) {
        if (rb - lb > 1) { // Проверка на лист
            int M = (lb + rb) / 2;
            l_child = new SegTree(lb, M);
            r_child = new SegTree(M, rb);
        }
    }
 
 
    // Добавляем элемент в ДО
    void update(std::vector<int> &arr, int ind, int val, int pred_ind) {
 
        max_ind_elem_di_pred_ind = std::max(max_ind_elem_di_pred_ind, {ind, arr[ind], val, pred_ind}, max_comp);
 
        // Есть ли дети
        if (l_child) {
            // k лежит либо в промежутке <l_child->lb, l_child->rb> либо в <r_child->lb, r_child->rb>
            if (arr[ind] < l_child->rb) {
                l_child->update(arr, ind, val, pred_ind);
            } else {
                r_child->update(arr, ind, val, pred_ind);
            }
        }
    }
 
    std::tuple<int, int, int, int> get_max(int lq, int rq) {
        if (lb >= lq && rb <= rq) {
            return max_ind_elem_di_pred_ind;
        }
 
        if (std::max(lb, lq) >= std::min(rb, rq))
            return {-1, -1, 0, -1};
 
        return std::max(l_child->get_max(lq, rq), r_child->get_max(lq, rq), max_comp);
    }
};
 
 
int main() {
    std::vector<int> arr = {1, 3, 4, 6};
    int n = arr.size();
 
    int max_elem_ind = std::max_element(arr.begin(), arr.end()) - arr.begin();
 
    SegTree MaxTree(0, arr[max_elem_ind] + 1);
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            MaxTree.update(arr, i, 1, -1);
        } else {
            MaxTree.update(arr, i, std::get<2>(MaxTree.get_max(0, arr[i])) + 1,
                           std::get<0>(MaxTree.get_max(0, arr[i])));
        }
    }
 
    std::tuple<int, int, int, int> ans_max = MaxTree.get_max(0, arr[max_elem_ind] + 1);
 
 
    int first_elem_of_max_lis = std::get<1>(ans_max),
            max_len_of_lis = std::get<2>(ans_max),
            pred = std::get<3>(ans_max);
 
    std::vector<int> ans(max_len_of_lis, first_elem_of_max_lis);
 
    for (int i = 1; i < max_len_of_lis; i++) {
        if (pred == -1) break;
        ans[i] = arr[pred];
        pred = std::get<3>(MaxTree.get_max(arr[pred], arr[pred] + 1));
    }
 
    for (int i = max_len_of_lis - 1; i >= 0; i--) {
        std::cout << ans[i] << " ";
    }
 
    return 0;
}