Нахождение суммы меньших элементов слева

я столкнулся с проблемой нахождения числа меньших элементов слева от каждого элемента в массиве целых чисел, который можно решить в O (nlgn), используя двоичные индексированные деревья (например, AVL и т.д.) или Merge Sort. Используя дерево AVL, можно вычислить размер левого поддерева для каждого элемента, и это будет необходимый ответ. Однако я не могу придумать, как эффективно вычислить сумму меньших элементов, оставшихся до каждого элемента. Для каждого элемента мне нужно пройти левое поддерево и суммировать значения в узлах или есть лучший способ (используя Merge Sort и т.д.)? Например, для массива: 4,7,1,3,2 требуемые анды будут: 0,4,0,1,1

Спасибо.

3 ответа

Отметьте этот учебник в двоичном индексированном дереве. Это структура, которая использует память O (n) и может выполнять такие задачи:  1. Измените значение a [i] на (to) x, назовите это add(i,x);  2. Возвращаем сумму всех [i], я <= m, назовем это get(x). в O (log n).

Теперь, как использовать это для вашей задачи. Вы можете сделать это за 2 шага. Первый шаг. Копирование, сортировка и удаление дубликатов из исходного массива. Теперь вы можете переназначить числа, поэтому они находятся в диапазоне [1... n]. Шаг 2. Теперь пройдите по массиву слева направо. Пусть A [i] - значение в исходном массиве, новое [i] - отображаемое значение. (если A = [2, 7, 11, -3, 7], то new = [2, 3, 4, 1, 2]).

Ответ: get (new [i] -1).

Обновить значения: add(new[i], 1) для подсчета, add(new[i], A[i]) для суммы.

В целом. Сортировка и переназначение O (n logn). Работа с массивом n * O (log n)= O (n log n). Таким образом, полная сложность O (n logn)

В качестве альтернативы используйте treap.

EDIT: Создание нового массива. Предположим, что исходный массив A = [2, 7, 11, -3, 7] Скопируйте его в B и отсортируйте, B = [-3, 2, 7, 7, 11] Сделайте уникальный B = [-3, 2, 7, 11]. Теперь, чтобы получить новый, вы можете

  • добавить все элементы для отображения в порядке возрастания, например. (-3 → 1, 2- > 2, 7- > 3, 11- > 4)
  • для каждого элемента в A, выполните двоичный поиск по B


В двоичных индексированных деревьях вы храните количество дочерних узлов для каждого node двоичного дерева поиска. Это позволяет вам найти количество узлов, предшествующих каждому node (количество меньших элементов).

Для этой задачи вы можете сохранить сумму дочерних node значений для каждого node двоичного дерева поиска. Это позволяет вам найти сумму значений для предыдущих узлов (сумма меньших элементов). Также в O (n * log (n)).


Следующий код имеет сложность O (nlogn). Для решения проблемы используется двоичное индексированное дерево.

#include <cstdio>
using namespace std;
const int MX_RANGE = 100000, MX_SIZE = 100000;
int tree[MX_RANGE] = {0}, a[MX_SIZE];
int main() {
 int n, mn = MX_RANGE, shift = 0;
 scanf("%d", &n);
 for(int i = 0; i < n; i++) {
 scanf("%d", &a[i]);
 if(a[i] < mn) mn = a[i]; 
 }
 shift = 1-mn; // we need to remap all values to start from 1
 for(int i = 0; i < n; i++) {
 // Read answer
 int sum = 0, idx = a[i]+shift-1;
 while(idx>0) {
 sum += tree[idx];
 idx -= (idx&-idx);
 } 
 printf("%d ", sum);
 // Update tree
 idx = a[i]+shift;
 while(idx<=MX_RANGE) {
 tree[idx] += a[i];
 idx += (idx&-idx);
 }
 }
 printf("\n");
}
</cstdio>

licensed under cc by-sa 3.0 with attribution.