Привет, я решал проблему с деревом сегментов, но я не могу внести небольшие изменения в функцию запроса дерева сегментов. На самом деле я хочу, чтобы моя функция запроса возвращала (int)(TotalArrayLength/3) максимальный элемент между индексами Qa и...

У меня проблемы с пониманием сложности дерева сегментов. Понятно, что если у вас есть функция обновления, которая должна изменить только один узел, ее сложность будет log(n). Но я понятия не имею, почему сложность запроса (a, b), где (a, b) -...

Я хотел бы решить проблему Иосифа Флавия, используя дерево сегментов. Я почти уверен, что простая симуляция (то есть линейный список) — это O(n^2) . Чего я хочу добиться, так это прыгать по массиву на определенное расстояние, взятое из дерева...

Есть ли способ использовать структуру дерева сегментов для вычисления частоты данного значения в массиве? Предположим, есть массив A размера N, и каждый элемент A[i] массива содержит значение 0, 1 или 2. Я хочу выполнить следующие операции:...

В дереве сегментов мы строим дерево сегментов над массивом. Например, если размер массива равен 8 [0-7], индексация. Количество узлов в дереве сегментов равно 15, т. е. 1, 2, 4, 8 на 1-м, 2-м, 3-м, 4-м уровнях Но в проблеме, если я объявлю...

Учитывая огромный массив целых чисел, оптимизируйте функции sum(i,j) и update(i,value) так, чтобы обе функции выполняли меньше O(n). Обновлять Это вопрос интервью. Я пробовал O(n) sum(i,j) и O(1) update(i, value). Другим решением является...

Учитывая список N чисел (1-индексированный), непрерывный блок является K-упорядоченным блоком, если он содержит более K одинаковых элементов, встречающихся последовательно. Пример : [2,4,4,5,5,5,3,3] имеет 3-порядковый блок от индекса 4 до 6 и...

Мне нужен алгоритм с некоторой структурой данных в Python, который на каждом шагу, когда даются два новых элемента e1, e2: находит позиции вставки (с сохранением порядка) первого и второго заданных элементов. находит максимальное значение...

Вам дан массив A, содержащий N целых чисел. Вам нужно работать с запросами Q в массиве. Запросы бывают двух типов. 1 U P: вам нужно обновить значение A u до P. 2 LRP: вам нужно найти A k такое, что A k - P минимально и A k > P и L‹=k‹= р...

Учитывая двоичный массив (элемент равен 0 или 1), мне нужно найти максимальную длину подмассива, содержащего все единицы для заданного диапазона (l и r) в массиве. Я знаю подход O (n) для поиска такого подмассива, но если есть запросы O (n), общая...

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