Префиксные суммы и два указателя

Префиксные суммы

Один из вариантов, когда нужно использовать алгоритм префиксные суммы, это определение чему равна сумма элементов на полуинтервале [L, R) или отрезке.

Пусть у нас есть массив nums из N чисел и необходимо ответить на запрос "Чему равна сумма элементов на полуинтервале [L, R)?"

Чтобы решить эту задачу нужно совершить предподсчет, некоторые предварительные действия с помощью которых мы потом сможем быстро отвечать на запрос.

Эти действия имеют смысл только если запросов много. Если не много то лучше просто пробежаться и посчитать.

Подсчитаем массив prefixsum длиной N+1, где prefixsum[k] будет хранить сумму всех чисел из nums с индексами от 0 до k-1.

Создадим массив префиксных сумм. Длина у него будет больше чем у исходного массива. И к-тый элемент этого массива будет равняться сумме всех чисел исходного массива с индексами от 0 до k-1. Такой массив легко посчитать за O(N^2). Но можно и еще быстрее.

Построение массива префиксных сумм

Для построения массива префиксных сумм не обязательно каждый раз складывать все значения по индексам. Достаточно взять предыдущую префиксную сумму и прибавить к ней очередное значение.

O(N): prefixsum[i] = prefixsum[i-1] + nums[i-1]

Индекс	0	1	2	3	4	5	6
nums	5	3	8	1	4	6
prefixsum	0	5	8	16	17	21	27

При составлении префиксного массива нужно помнить 2 вещи:

Массив префиксных сумм должен быть на 1 больше, чем исходный!
Переполнение. Целые числа могут переполнить допустимое значение. При сложении 2х int значений, при переполнении получается не верный результат. Если складывать long + int то значение будет приведено к типу long

Ответ на запрос суммы на полуинтервале

Ответ за O(1): sum(L, R) = prefixsum[R] - prefixsum[L]
Найдем sum(2, 5) = prefixsum[5] - prefixsum[2] = 21 - 8 = 13

Почему мы ищем полуинтервал? Чтобы избежать проблемы запросов прижатых к левому краю. Если мы будем искать значение от 0 до 3, как для полуинтервала, то все будет корректно. А если считать как для отрезка то чтобы взять значение прижатое к левому краю нам пришлось бы выйти за пределы массива и взять элементс индексом -1.

Реализация RSQ(Range Summ Query) через префиксные суммы

public static long[] makePrefixSum(int[] nums) {
      long[] prefixsum = new long[nums.length + 1];
      for (int i = 1; i < nums.length + 1; i++) {
          prefixsum[i] = prefixsum[i - 1] + nums[i - 1];
      }
      return prefixsum;
  }

  public static long rsq(long[] prefixsum, int l, int r) {
      return prefixsum[r] - prefixsum[l];
  }

Пример задачи:

Пусть на сайт заходят люди и для каждого человека записано, когда он зашел. Нужно посчитать сколько людей у нас было на сайте с L дня по R.Получится массив где в каждом элементе будет храниться число человек посетивших сайт в этот день. И далее с помощью алгоритма префиксных сумм можно ответить на целевой вопрос.

Задача 1

Дана последовательность чисел длиной N и M запросов

Запросы: Сколько нулей на полуинтервале [l, R)

Решение за O(NM)

Для каждого запроса переберем все числа от L до R (не включительно) и считаем количество нулей. В худшем случае каждый запрос за O(N). Так как всего запросов M то общая сложность решения O(NM).

public static int countZeroes(int[] nums, int l, int r) {
    int cnt = 0;
    for (int i = l; i < r; i++) {
        if(nums[i] == 0){
            cnt+=1;
        }
    }
    return cnt;
}

Решение за O(N+M)

Попробуем применить метод префиксных сумм. Вместо префиксных сумм будем считать количество нулей на префиксе.

Для каждого префикса посчитаем количество нулей на нем (prefixZeroes). Тогда ответ на запрос на полуинтервале [L, R): prefixZeroes[R] - prefixZeroes[L].

	0	1	2	3	4	5	6	7
nums	1	0	1	1	0	0	1
prefixZeroes	0	0	1	1	1	2	3	3

public static long[] makePrefixZeroes(int[] nums) {
    long[] prefixsum = new long[nums.length + 1];
    for (int i = 1; i < nums.length + 1; i++) {
        if(nums[i-1] == 0){
            prefixsum[i] = prefixsum[i - 1] + 1;
        }else{
            prefixsum[i] = prefixsum[i - 1];
        }
    }
    return prefixsum;
}

public static long countZeroes(long[] prefixZeroes, int l, int r) {
    return prefixZeroes[r] - prefixZeroes[l];
}

Получается сложность O(N+M). O(N) уйден на построение тк у нас N элементов. И на каждый из M запросов мы отвечаем за O(1).

Задача 2

Дана последовательность чисел длиной N. Необходимо найти количество отрезков с нулевой суммой.

Решение за $O(N^3)$

Переберем начало и конец отрезка и просто просуммируем все его элементы.

Перебираем левую и правую границу отрезка и перебираем цифры которые находятся между ними.

public static int countZeroSumRanges(int[] nums) {
    int cntRanges = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length + 1; j++) {
            int rangeSum = 0;
            for (int k = i; k < j; k++) {
                rangeSum += nums[k];
            }
            if (rangeSum == 0) {
                cntRanges += 1;
            }
        }
    }
    return cntRanges;
}

Решение за $O(N^2)$

Переберем начало и будем двигать конец, сумируя элементы.

Фиксируем значение слева и затем двигая от этой точки указатель правого края высчитываем сумму. Нам не нужно каждый раз заново высчитывать всю сумму.

public static int countZeroSumRanges(int[] nums) {
    int cntRanges = 0;
    for (int i = 0; i < nums.length; i++) {
        int rangeSum = 0;
        for (int j = i; j < nums.length; j++) {
            rangeSum += nums[j];
            if (rangeSum == 0) {
                cntRanges += 1;
            }
        }
    }
    return cntRanges;
}

Решение за $O(N)$

Насчитаем префиксные суммы. Одинаковые префиксные суммы означают, что сумма на отрезке с началом и концом в позициях, на которых достигаются одинаковые префиксные суммы, будет равна нулю.

Проходим по массиву и считаем префиксые суммы, при подсчете в словаре увеличиваем количество точек в этой сумме на 1.
Проходим по словарю и для каждой суммы высчитываем количество пар сочетаний по комбинаторной формуле, где k = 2 так как ищем пару

${C_{n}^{k}} = \frac{n!}{k!(n-k)!} = \frac{n \times (n -1) \times (n - 2)!} {2! \times (n - 2)!} = \frac{n \times (n - 1)} {2}$

public static Map<Integer, Integer> countPrefixSums(int[] nums) {
    Map<Integer, Integer> prefixSumByValue = new HashMap<>();
    {
        prefixSumByValue.put(0, 1);
    }
    int nowSum = 0;
    for (int now : nums) {
        nowSum += now;
        if (!prefixSumByValue.containsKey(nowSum)) {
            prefixSumByValue.put(nowSum, 0);
        }
        prefixSumByValue.put(nowSum, prefixSumByValue.get(nowSum) + 1);
    }
    return prefixSumByValue;
}

public static int countZeroSumRanges(Map<Integer, Integer> prefixSumByValue) {
    int cntRanges = 0;
    for (Integer nowSum : prefixSumByValue.keySet()) {
        int cntSum = prefixSumByValue.get(nowSum);
        cntRanges += cntSum * (cntSum - 1) / 2;
    }

    return cntRanges;
}

Два указателя

Задача 1

Дана отсортированная последовательность чисел длиной N и число K. Необходимо найти количество пар чисел A, B, таких что B - A > K.

Решение за $O(N^2)$

Переберем все пары чисел и для каждой проверим условие.

Во вложенном цикле можно идти не каждый раз сначала перебирая цифры, а дигаясь вправо от левой границы.

public static int cntPairsWithDiffGtk(int[] sortedNums, int k) {
    int cntPairs = 0;
    for (int i = 0; i < sortedNums.length; i++) {
        for (int j = i; j < sortedNums.length; j++) {
            if (sortedNums[j] - sortedNums[i] > k) {
                cntPairs += 1;
            }
        }
    }
    return cntPairs;
}

Решение за $O(N)$

Возьмем наименьшее число и найдем для него первое подходящее большее. Все еще большие числа точно подходят. Возьмем в качестве меньшего числа следующее, а указатель первого подходящего большего будем двигать начиная с той позиции, где он находится сейчас

public static int cntPairsWithDiffGtk(int[] sortedNums, int k) {
    int cntPairs = 0;
    int last = 0;
    for (int first = 0; first < sortedNums.length; first++) {

        while (last < sortedNums.length && sortedNums[last] - sortedNums[first] <= k) {
            last += 1;
        }
        cntPairs += sortedNums.length - last;
    }
    return cntPairs;
}

Задача 2

Игрок в футбол обладает одной числовой характеристикой - профессионализмом. Команда называется сплоченной, если профессионализм любого игрока не превосходит сумарный профессионализм любых других двух игроков из команды. Команда может состоять из любого количества игроков. Дана отсортированная последовательность чисел длиной N - профессионализм игроков.

Необходимо найти максимальный суммарный профессионализм сплоченной команды.

public static int bestTeamSum(int[] players) {
    int bestSum = 0;
    int nowSum = 0;
    int last = 0;
    for (int first = 0; first < players.length; first++) {

        while (last < players.length && (last == first || players[last] + players[first] >= players[last]) {
            nowSum += players[last];
            last += 1;
        }
        bestSum = bestSum >= nowSum ? bestSum : nowSum;
        nowSum -= players[first];
    }
    return bestSum;
}

Задача 3

Даны две отсортированные последовательности чисел (длиной N и M соответсвенно)

Необходимо слить их в одну отсортированную последовательность.

Решение

Две последовательности могуть быть не обязательно одинаковые по длине, могут быть одинаковые числа.

Идея решения: делаем указатель на текущий элемент первой и во второй последовательности и просто выводим то что меньше по текущему указателю. Например, из чисел из 1 и 3 меньше 1 - 1 записали в ответ и указатель двинули в той последовательности из которой мы взяли очередное число и так далее. Если одна из последовательностей заканчивается мы просто выписываем весь оставшийся хвост текущей последовательности.

Неидеальная реализация

Поставим два указателя на начало каждой из последовательностей. Выберем тот, который указывает на меньшее число, запишем это число в результат и сдвинем указатель

Смотрите также:

Префиксные суммы и два указателя