Может ли кто-нибудь помочь мне с деревьями 2D / 3D сегментов - PullRequest
Новая
       38

Может ли кто-нибудь помочь мне с деревьями 2D / 3D сегментов

0 голосов
/ 27 марта 2019

Я пытаюсь решить задачу: Дана функция. Одним из аргументов функции является массив. Это может быть 1-мерное / 2-мерное или 3-мерное. Остальные параметры: функция суммы и нейтральное число. Будет 0. Мне нужно построить дерево сегментов (1D / 2D / 3D), в зависимости от входящего массива и рассчитать сумму диапазона. Может кто-нибудь дать мне подсказку?

Я написал функцию, которая строит дерево 2D-сегментов. Код ниже: 

function recursiveSegmentTree(array, fn, N) {
    var t = new Array(array.length * 16);

    //Building X2D segment tree
    function build_Y(vx, lx, rx, vy, ly, ry, array){
        if (ly == ry){
            if (lx == rx){
                t[vx][vy] = array[lx][ly];
            }else{
                t[vx][vy] = fn(t[2 * vx][vy], t[2 * vx + 1][vy]);
            }
        }else{
            let vmiddleY = Math.floor((ry + ly) / 2);
            build_Y(vx, lx, rx, 2 * vy, ly, vmiddleY, array);
            build_Y(vx, lx, rx, 2 * vy + 1, vmiddleY + 1, ry, array);
            t[vx][vy] = fn(t[vx][2 * vy], t[vx][2 * vy + 1]);
        }
    }

    function build_X(vx, lx, rx, array){
        if (lx != rx){
            let vmiddleX = Math.floor((rx + lx) / 2);
            build_X(2 * vx, lx, vmiddleX, array);
            build_X(2 * vx + 1, vmiddleX + 1, rx, array);
        }
        build_Y(vx, lx, rx, 1, 0, array.length - 1, array);
    }

    //Calculating sum
    function finalQuery(pos, start, end, x1, x2, node, array, N){
        if (x2 < start || x1 > end){
            return N;
        }
        if (x1 <= start && end <= x2){
            return t[node][pos];
        }
        let mid = Math.floor((start + end) / 2);
        let p1 = finalQuery(2 * pos, start, mid, x1, x2, node, array, N);
        let p2 = finalQuery(2 * pos + 1, mid + 1, end, x1, x2, node, array, N);
        let result = fn(p1, p2);
        return fn(N, result);
    }

    function query(pos, start, end, y1, y2, x1, x2, array, N){
        if (y2 < start || end < y1){
            return 0;
        }
        if (y1 <= start && end <= y2) {
            return finalQuery(1, 0, 3, x1, x2, pos, array, N);
        }
        let mid = Math.floor((start + end) / 2);
        let p1 = query(2 * pos, start, mid, y1, y2, x1, x2, array, N);
        let p2 = query(2 * pos + 1, mid + 1, end, y1, y2, x1, x2, array, N);
        let result = fn(p1, p2);
        return fn(N, result);
    }
    for (let i = 0; i < (array.length * 16); i++){
        t[i] = new Array(array.length * 16);
    }

    return function (from, to) {

        if (from < 0 || array.length < to){
            throw new Error("Out of range");
        }
        if (to < from) {
            throw new Error("From is greater");
        }
        if (from == to) { return N; }

        let result = N;

        if (Array.isArray(array[0]) == false){

            array.slice(from, to).forEach((arr) => {
                if (!Array.isArray(arr)) {
                    result += arr;
                }
                else {
                    result += fn(result, arr);
                }
            });
        } else if (Array.isArray(array[0]) == true){

            build_X(1, 0, array.length - 1, array);
            console.log(t);
            result = query(1, 0, array.length - 1, from, to - 1, from, to - 1, array, N);
        }
        return result;
    };
};
...