[PROOF OF CONCEPT] node_update class for __gnu_pbds::tree that allows for O(log n) RMQ capabilities

rmq_node_update.hpp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

struct met {
    int lo, hi, max_v;
};

template<typename Node_CItr, typename Node_Itr, typename Cmp_Fn, typename _Alloc>
class rmq_node_update {
    private:
        virtual Node_Itr node_begin() = 0;
        virtual Node_Itr node_end() = 0;
        int rmq_util(int left, int right, Node_Itr n) {
            int ans = 0;
            met d = n.get_metadata();
            if (left >= d.hi || right <= d.lo) {
                //cout << "Node " << (*n)->first << ", " << (*n)->second << ": " << "Out of range (lo " << d.lo << " hi " << d.hi << ")\n";
                return 0;
            }
            int k = (*n)->first;
            if (left <= k && right > k) {
                ans = max(ans, d.max_v);
            }
            if (left <= d.lo && right >= d.hi) {
                //cout << "Node " << (*n)->first << ", " << (*n)->second << ": " << "Fully in range (" << d.max_v << ")\n";
                return ans;
            }
            Node_Itr l = n.get_l_child();
            Node_Itr r = n.get_r_child();
            if (l != node_end()) {
                ans = max(ans, rmq_util(left, right, l));
            }
            if (r != node_end()) {
                ans = max(ans, rmq_util(left, right, r));
            }
            //cout << "Node " << (*n)->first << ", " << (*n)->second << ": " << "Partially in range (" << ans << ")\n";
            return ans;
        }
    public:
        typedef met metadata_type;
        typedef typename _Alloc::template rebind<metadata_type>::other::reference ree;
        
        // Maintains invariant
        // PRE: All descendants have invariant maintained
        //      All the ranges combine to make a contiguous section
        void operator()(Node_Itr node, Node_CItr end) {
            //cout << "Maintaining invariant for key " << (**node).first << "\n";
            Node_Itr l = node.get_l_child();
            Node_Itr r = node.get_r_child();
            met lm = { (*node)->first, (*node)->first + 1, 0 };
            met rm = { (*node)->first, (*node)->first + 1, 0 };
            if (l != end) {
                lm = l.get_metadata();
            }
            if (r != end) {
                rm = r.get_metadata();
            }
            int l_max = lm.max_v;
            int r_max = rm.max_v;
            const int self_max = (*node)->second;
            //cout << "l_max: " << l_max << "\nr_max: " << r_max << "\nself_max: " << self_max << "\n";
            int ans = max(self_max, max(l_max, r_max));
            const_cast<ree>(node.get_metadata()) = { min(lm.lo, rm.lo), max(lm.hi, rm.hi), ans };
        }

        int rmq(int left, int right) {
            return rmq_util(left, right, node_begin());
        }
};

// Example usage: 
typedef tree<int, int, less<int>, rb_tree_tag, rmq_node_update> tr;