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

Question

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

Спасибо.

Answer 1

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

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

Answer 2

Проверить this tutorial на двоичном индексированном дереве. Это структура, которая использует память O (n) и может выполнять такие задачи:
1. Измените значение [i] на (to) x, назовите это add(i,x);
2. Возвращаемая сумма все [i], 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]).

Ответ получен (новый [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].
Теперь, чтобы получить новые, вы можете

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

Answer 3

Следующий код имеет сложность 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"); 
}