Как найти сумму элементов от данного индексного интервала (я, j) в постоянное время?
Учитывая массив. Как мы можем найти сумму элементов в индексном интервале (i, j) в постоянное время. Вам разрешают использовать дополнительное пространство.
Пример:
A: 3 2 4 7 1 - 2 8 0 - 4 2 1 5 6 - 1
длина = 14
int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);
сумма должна быть 10 в постоянное время.
2 ответа
Если вы можете потратить O (n) времени на «подготовку» вспомогательной информации, на основе которой вы сможете вычислять суммы за O (1), вы могли бы легко это сделать.
Подготовка (O (n)):
aux[0] = 0;
foreach i in (1..LENGTH) {
aux[i] = aux[i-1] + arr[i];
}
Запрос (O (1)), arr пронумерован от 1 до ДЛИНА :
sum(i,j) = aux[j] - aux[i-1];
Я думаю, что это было намерением, потому что иначе было бы невозможно: для любой длины вычислить sum (0, length-1) вы должны были просканировать весь массив; это занимает по крайней мере линейное время.
Это невозможно сделать вместе nМгновенное время, если вы не сохраните информацию.
Вам нужно будет сделать что-то вроде специальной модификации массива для хранения для каждого индекса суммы всех значений между началом массива и этим индексом, а затем использовать вычитание в диапазоне, чтобы получить разницу в суммах.
Однако, похоже, ничто в вашем примере кода не позволяет этого. Массив создается пользователем (и может быть изменен в любой момент), и вы не можете его контролировать.
Любой алгоритм, который должен сканировать группу элементов в последовательном несортированном списке, будет O (n).