вопрос про скорость работы алгоритмов

Question

Имеется задача: создать класс с указанными методами:

class NumArray {
  
    public NumArray(int[] nums) {
    //инициализация объекта с массивом интов
    }

    public void update(int index, int val) {
    // изменить значение под индексом index на значение val
    }

    public int sumRange(int left, int right) {
    //посчитать сумму между левым и правым индексом включительно
    }
}

Казалось бы ничего трудного, но я и реализовал это самым очевидным способом:

class NumArray {
    int[] nums;
    public NumArray(int[] nums) {
        this.nums=nums;
    }

    public void update(int index, int val) {
        nums[index]=val;
    }

    public int sumRange(int left, int right) {
        int sum=0;
        for(int i=left;i<=right;i++)
            sum+=nums[i];
        return sum;
    }
}

Класс прошел 13/15 проверок и на 14 когда я получил на вход большие массивы и большую разницу между left и right я не прошел проверку - не вписался в лимит по времени. Подсмотрел в ответы - там люди бинарные деревья организовывают и прочие "сложности". И я не могу понять ЗАЧЕМ? По сути методы в моем виде итак максимально быстрые? (update - это O(1) - и быстрее сделать невозможно) и (sumRange - это О(n) - так же быстрее сделать невозможно). В чем я ошибаюсь? Заранее спасибо

Answer 1

Вообщем благодаря подсказкам в комментариях решил задачу. Воспользовался структурой данных "дерево отрезков". Действительно при таком варианте решения я все также никуда не делся от сложности O(n) - именно такая сложность при построении дерева. Поэтому этот вариант помогает выиграть в скорости, когда у нас есть ОДИН исходный массив, и множество манипуляций с ним. То есть строится дерево 1 раз со сложностью О(n), а далее все манипуляции проводятся уже за логарифмическое время. И благодаря этому я проскочил те тесты, где задается один массив, и множественные вызовы методов на нем. Собственно сама реализация класса, если вдруг кому понадобится:

   public NumArray(int[] nums) {
        this.nums = nums;
        if (nums == null || nums.length == 0) return;
        this.root = buildTree(0, nums.length - 1);   //запуск построения дерева
        //System.out.println(this.root);
    }

    private TreeNode buildTree(int start, int end) {       //построение дерева
        TreeNode treeNode = new TreeNode();
        treeNode.start = start;
        treeNode.end = end;

        if (start == end) {
            treeNode.sum = nums[start];
            //System.out.println(treeNode.sum);
            return treeNode;
        }
        int mid = start + (end - start) / 2;
        treeNode.left = buildTree(start, mid);
        treeNode.right = buildTree(mid + 1, end);

        treeNode.sum = treeNode.left.sum + treeNode.right.sum;
        //System.out.println(treeNode.sum);

        return treeNode;
    }

    public void update(int i, int val) {
        update(root, i, val);               //стартовый запуск метода update, в котором уже будут крутиться рекурсии
    }

    private void update(TreeNode node, int i, int val) {
        if (node == null) return;
        if (node.end == node.start) {
            node.sum = val;
            return;
        }
        int mid = node.start + (node.end - node.start) / 2;
        if (i <= mid)
            update(node.left, i, val);
        else update(node.right, i, val);
        node.sum = node.left.sum + node.right.sum;
    }

    public int sumRange(int start, int end) {
        return sumRange(root, start, end);        // аналогично стартовый запуск метода sumRange, в котором будет крутиться рекурсия.
    }

    private int sumRange(TreeNode node, int start, int end) {
        if (start < node.start || end > node.end) {
            return -1;
        }

        if ((start == node.start) && (end == node.end)) {
            return node.sum;
        }

        int mid = node.start + (node.end - node.start) / 2;
        if (start > mid)
            return sumRange(node.right, start, end);
        if (end <= mid) {
            return sumRange(node.left, start, end);
        }
        return sumRange(node.left, start, mid) + sumRange(node.right, mid + 1, end);

    }
}

Всем спасибо, за подсказки!

БЛОГ НА HUSL

вопрос про скорость работы алгоритмов

Ответы (1 шт):