как ни странно, этот написанный за 15 минут кусок кода сработал с первого раза:

int query_recursive(const int node, const int l, const int r)
{
    int min1 = INT_MAX, min2 = INT_MAX, min3 = INT_MAX;
    if (r - l + 1 == tree[node].leaf_count)
        return tree[node].min;
    if (tree[tree[node].child[0]].leaf_count >= l)
        min1 = query_recursive(tree[node].child[0], l, (tree[tree[node].child[0]].leaf_count < r) ? tree[tree[node].child[0]].leaf_count : r);
    if (l <= tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count)
        min2 = query_recursive(tree[node].child[1], (l - tree[tree[node].child[0]].leaf_count >= 1) ? l - tree[tree[node].child[0]].leaf_count : 1, (tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count < r) ? tree[tree[node].child[1]].leaf_count : r - tree[tree[node].child[0]].leaf_count);
    if (tree[node].child[2])
        if (tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count < r)
            min3 = query_recursive(tree[node].child[2], (l - (tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count) >= 1) ? l - (tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count) : 1, r - (tree[tree[node].child[0]].leaf_count + tree[tree[node].child[1]].leaf_count));
    return (((min1 < min2) ? min1 : min2) < min3) ? ((min1 < min2) ? min1 : min2) : min3;
}