Использование сегмента дерева для решения проблемы 307, которая является запросом диапазона значений - изменяемый в коде leetecode, но время превышено - PullRequest
Новая
       40

Использование сегмента дерева для решения проблемы 307, которая является запросом диапазона значений - изменяемый в коде leetecode, но время превышено

0 голосов
/ 09 мая 2019

Я программирую проблему 307 в leetcode, которая является изменяемой проблемой Range Sum Query Mutable.Я использовал дерево сегментов, чтобы решить это.Я думаю, что время не превысит проблему, потому что его сложность для обновления - log (n).Но после того, как я отправляю свой код в систему, я получаю подсказку о превышении времени.Отображение моего кода прошло через девять более десяти тестовых примеров.Я вставляю свой код сюда, чтобы получить советы о том, как улучшить производительность моего кода. 

public class NumArray {

    private int[] data;
    private int[] tree;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            data = new int[nums.length];
            tree = new int[nums.length*4];
            for (int i = 0; i < nums.length; i++) {
                data[i] = nums[i];
            }

            buildTree(0, 0, data.length-1);
        }
    }

    public void buildTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }

        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        buildTree(leftTreeIndex, l, mid);
        buildTree(rightTreeIndex, mid+1, r);

        tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
    }

    private int leftChild(int index) {
        return index*2 + 1;
    }

    private int rightChild(int index) {
        return index*2 + 2;
    }

    public int sumRange(int i, int j) {
        return sumRange(0, 0, data.length-1, i, j);
    }

    private int sumRange(int treeIndex, int l, int r, int queryL, int queryR) {
        System.out.println("treeIndex: " + treeIndex);
        if (l == queryL && r == queryR)
            return tree[treeIndex];

        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if (queryR <= mid) {
            return sumRange(leftTreeIndex, l, mid, queryL, queryR);
        } else if (queryL > mid) {
            return sumRange(rightTreeIndex, mid + 1, r, queryL, queryR);
        } else {
            int leftRes = sumRange(leftTreeIndex, l, mid, queryL, mid);
            int rightRes = sumRange(rightTreeIndex, mid + 1, r, mid + 1, queryR);
            return leftRes + rightRes;
        }
    }

    public void update(int index, int val) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index is illegal");
        }

        data[index] = val;
        update(0, 0, data.length-1, index, val);
    }

    private void update(int treeIndex, int l, int r, int index, int val) {
        if (l == r) {
            tree[treeIndex] = val;
            return;
        }

        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        if (index <= mid) {
            update(leftTreeIndex, l, mid, index, val);
        } else {
            update(rightTreeIndex, mid+1, r, index, val);
        }

        tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
        return;
    }

}
...