Algorithms: Range Queries

function segment_build(array $a, array &$tree): int {
    alg_require(array_is_list($a));
    alg_require(array_is_list($tree));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    alg_require((count($tree) == alg_mul(2, $n)));
    alg_require(($n >= 1));
    $i = 0;
    $tree[0] = 0;
    while (($i < $n)) {
        $tree[alg_add($n, $i)] = $a[$i];

    static int fenwick_sum(int[] tree, int end) {
        java.util.Objects.requireNonNull(tree, "tree");
        int n = Math.subtractExact(tree.length, 1);
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require((tree.length == Math.addExact(n, 1)));
        alg_require(((end >= 0) && (end <= n)));
        int total = 0;
        while ((end > 0)) {
            total = Math.addExact(total, tree[end]);
            end = Math.subtractExact(end, (end & Math.negateExact(end)));
        }
        return total;

function fenwick_sum(tree, end) {
    alg_require(tree instanceof Int32Array);
    alg_require(Number.isInteger(end) && end >= -2147483648 && end <= 2147483647);
    let n = alg_sub(tree.length, 1);
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require((tree.length == alg_add(n, 1)));
    alg_require(((end >= 0) && (end <= n)));
    let total = 0;
    while ((end > 0)) {
        total = alg_add(total, tree[end]);
        end = alg_sub(end, (end & alg_sub(0, end)));
    }

def fenwick_sum(tree: list[int], end: int) -> int:
    alg_require(isinstance(tree, (list, tuple)) and len(tree) <= 1000000)
    alg_require(type(end) is int and -2147483648 <= end <= 2147483647)
    n: int = len(tree) - 1
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(tree) == n + 1)
    alg_require(end >= 0 and end <= n)
    total: int = 0
    while end > 0:
        total += tree[end]
        end -= end & -end
    return total

int fenwick_sum(const int *tree, size_t tree_length, int end) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    if (tree_length > 1000000 || (tree_length && !tree)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = alg_sub((int)tree_length, 1, &alg_error);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)tree_length == alg_add(n, 1, &alg_error)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((end >= 0) && (end <= n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }