LCA with RMQ

#include <iostream>
#include <vector>
#include <cstring>
#define MAX_N 500
#define MAX (1 << 10)
using namespace std;

int depth[2*MAX_N], t_sequence[2*MAX_N], first_ocurrence[MAX_N], indx;
int tree[MAX], lazy[MAX];
vector<vector<int> > children(MAX_N);

void build_tree(int node, int a, int b) {
    if(a > b) return; // Out of range

    if(a == b) { // Leaf node
            tree[node] = first_ocurrence[a]; // Init value
        return;
    }

    build_tree(node*2, a, (a+b)/2); // Init left child
    build_tree(node*2+1, 1+(a+b)/2, b); // Init right child

    tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value
}

/**
 * Increment elements within range [i, j] with value value
 */
void update_tree(int node, int a, int b, int i, int j, int value) {

    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it

        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
                lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }

        lazy[node] = 0; // Reset it
    }

    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
        return;

    if(a >= i && b <= j) { // Segment is fully within range
            tree[node] += value;

        if(a != b) { // Not leaf node
            lazy[node*2] += value;
            lazy[node*2+1] += value;
        }

            return;
    }

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child

    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}

/**
 * Query tree to get max element value within range [i, j]
 */
int query_tree(int node, int a, int b, int i, int j) {

    if(a > b || a > j || b < i) return -inf; // Out of range

    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it

        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }

        lazy[node] = 0; // Reset it
    }

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];

    int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
    int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child

    int res = max(q1, q2); // Return final result

    return res;
}

void dfs(int current, int dep){
    first_ocurrence[current] = indx;
    t_sequence[indx] = current;
    depth[indx++] = dep;

    for (int i = 0; i < children[current].size(); i++){
        dfs(children[current][i], dep + 1);
        t_sequence[indx] = current;
        depth[indx++] = dep;
    }
}

void build(int root){
    indx = 0;
    memset(first_ocurrence, -1, sizeof(first_ocurrence));
    dfs(root, 0);
}



int main(){
    //Build the tree
    build(root);
    build_tree(0,0,cant_nodos);

    return 0;
}