Dynamic Range Minimum Queries

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

#define INIT_VALUE UINT64_MAX

uint64_t n = 0;
uint64_t q = 0;
uint64_t tab_len = 0;
uint64_t *tree;

uint64_t f(uint64_t a, uint64_t b){
    return a < b ? a : b;
}

void init_tree(){
    for(uint64_t i = tab_len - 1; i >= 1; i--)
        tree[i] = f(tree[2*i], tree[2*i+1]);
}

void insert_tree(uint64_t index, uint64_t value){
    tree[tab_len + index] = value;
    for(uint64_t i = (tab_len + index)/2; i >= 1; i/=2)
        tree[i] = f(tree[2*i], tree[2*i+1]);
}

uint64_t find_range(uint64_t a, uint64_t b){
    a += tab_len;
    b += tab_len;
    uint64_t acc = INIT_VALUE;
    while (a <= b){
        if (a%2 == 1)
            acc = f(acc, tree[a++]);
        if (b%2 == 0)
            acc = f(acc,tree[b--]);
        a /= 2;
        b /= 2;
    }
    return acc;
}


int main() {
    if (scanf("%ld %ld", &n, &q) == 0)
        return EXIT_FAILURE;

    // case n=0 is not supposed to happen.

    tab_len = n;

    // rounding to the next power of two, adapted for 64 integer from https://graphics.stanford.edu/%7Eseander/bithacks.html#RoundUpPowerOf2
    tab_len--; // so powers of two become stay constant after all operations;
    tab_len |= tab_len >> 1;
    tab_len |= tab_len >> 2;
    tab_len |= tab_len >> 4;
    tab_len |= tab_len >> 8;
    tab_len |= tab_len >> 16;
    tab_len |= tab_len >> 32;
    tab_len++;

    tree = (uint64_t *) calloc(tab_len*2, sizeof(uint64_t));
    // tree--; // the element of index 0 should never be accessed;


    for (uint64_t i = 0; i < n; i++)
        if (scanf("%ld", tree + tab_len + i) == 0)
            return EXIT_FAILURE;
    for (uint64_t i = n; i < tab_len; i++)
        tree[tab_len + i] = INIT_VALUE;

    init_tree();

    // for(uint64_t i = 0; i < tab_len * 2; i++)
    //     printf("%ld, ", tree[i]);
    // printf("\n"); 

    // main algo
    uint64_t t, a, b;
    for (uint64_t i = 0; i < q; i++){
        if (scanf("%ld %ld %ld", &t, &a, &b) == 0)
            return EXIT_FAILURE;
        if (t == 1)
            insert_tree(a-1, b);
        else
            printf("%ld\n", find_range(a-1, b-1));
    }




    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED