Комментарии 11
Двенадцатую задачу можно также решить с подготовкой за 
и ответом на запрос за 
, используя алгоритм алгоритм Фараха-Колтона и Бендера.
Решение первой задачи с помощью "префиксных сумм", так как это показано в статье, возможно лишь для очень маленьких значений чисел в входном массиве. В противном случае легко нарваться на переполнение при вычислении running sum (переменная "b"). Если задачку содрали из Leetcode.com то нужно было полностью скопировать и условия к задаче. В Leetcode для подобных задач четко прописываются пограничные условия (в данном случае - на размер входного массива и на динамический диапазон числе в массиве).
Решение может быть стабилизировано переопределением типа префиксного массива и типа переменной "b" на 64-битовый тип std::int64_t или long long int (https://en.cppreference.com/w/cpp/language/types). При этом размер массива должен быть ограничен 2**32 элементами.
Mip-mapping на видеокартах
А вот такая задача: реализовать функцию inc_argmin(i, v), которая увеличивает i-й элемент на v и возвращает индекс минимального элемента. Можно считать, что изначально массив устроен тривиально, например, заполнен одинаковым значением.
Есть ли решение со сложностью O(1)?
Кажется, это невозможно без дополнительных ограничений.
Этой функцией массив можно отсортировать за O(N), независимо от размеров чисел. Заполним сначала n вызовами массив исходными числами, а потом за n-1 раз последний минимальный индекс уводим в бесконечность, прибавляя большое число. Так получим индексы всех чисел в порядке возрастания.
Чисто за O(N) работающей сортировки без какого-то ограничения на числа, по-моему, не существует.
Так что оно возможно только для небольших суммарных значений v (пусть сумма всех значений v для любого индекса не превосходит MaxV = O(N) где N - количество операций).
Тогда можно завести MaxV списков. Каждый элемент массива будет в одном двусвязном списке, соответствующим его значению. Сначала все индексы виртуально-лениво сложим в список для начального значения. При выполнении операции удаляем индекс из текущего его списка и кладем в список на +v позиций. Для этого надо для каждого элемента хранить указатель на него в каком-то двусвязном списке. Если список с минимальным значением опустел, переходим к следующему не пустому. Это обработает N операций за O(N + MaxV).
А можно примеры реальных предметных областей где это может применяться?
В видео кодеках. Вот пример из vp9. Но тут не очень понятно, может тут немного другое. В браузерах. Вот пример из хрома. Точно применяется во всяких игровых движках. Скорее всего применяется в каких-нибудь базах данных (в географических индексах, например). Наверняка применяется в недрах операционных систем.
Может применятся вообще везде, где у вас что-то хоть немного сложнее перекладывания json-ов и формошлепства.
Range aggregation queries (SELECT average(weight) WHERE age BETWEEN 30 AND 40)
https://petsymposium.org/popets/2022/popets-2022-0128.pdf
Top-k completion (вы что-то написали в текстовом поле, а вам дают 10 продолжений)
https://dl.acm.org/doi/pdf/10.1145/2488388.2488440
Least common ancestor problem и её применения (анализ иерархии классов, зависимостей модулей)
Сбор статистики на в потоке данных
https://www.sciencedirect.com/science/article/pii/S0169023X10000753
Succint словари
https://en.wikipedia.org/wiki/Succinct_data_structure#Succinct_indexable_dictionaries
Дерево отрезков