Как посчитать количество инверсий в массиве, используя деревья сегментов

Позвольте мне объяснить шаг за шагом с примером:

arr      :  4 3 7 1
position :  0 1 2 3

Сначала отсортируйте массив в порядке убывания по паре {значение, индекс}.

arr      :  7 4 3 1
index    :  2 0 1 3
position :  0 1 2 3

Итерация слева направо для каждого элемента arr[i] —

Запрос для каждого элемента index (запрос на диапазон [0, arr[i].index] чтобы получить большее количество чисел на левой стороне) и поместить результат запроса в соответствующий index выходного массива.

После каждого запроса увеличивайте соответствующий узел дерева сегментов, который покрывает index,

Таким образом, мы обеспечиваем получение только большего числа 0 в index - 1 в качестве значений только больше, чем arr[i] были вставлены до сих пор.

Ниже реализация C ++ будет иметь больше смысла.

class SegmentTree {

vector<int> segmentNode;

public:
void init(int n) {
int N = /* 2 * pow(2, ceil(log((double) n / log(2.0)))) - 1 */ 4 * n;
segmentNode.resize(N, 0);
}

void insert(int node, int left, int right, const int indx) {
if(indx < left or indx > right) {
return;
}
if(left == right and indx == left) {
segmentNode[node]++;
return;
}
int leftNode = node << 1;
int rightNode = leftNode | 1;
int mid = left + (right - left) / 2;

insert(leftNode, left, mid, indx);
insert(rightNode, mid + 1, right, indx);

segmentNode[node] = segmentNode[leftNode] + segmentNode[rightNode];
}

int query(int node, int left, int right, const int L, const int R) {
if(left > R or right < L) {
return 0;
}
if(left >= L and right <= R) {
return segmentNode[node];
}

int leftNode = node << 1;
int rightNode = leftNode | 1;
int mid = left + (right - left) / 2;

return query(leftNode, left, mid, L, R) + query(rightNode, mid + 1, right, L, R);
}

};

vector<int> countGreater(vector<int>& nums) {
vector<int> result;
if(nums.empty()) {
return result;
}
int n = (int)nums.size();
vector<pair<int, int> > data(n);
for(int i = 0; i < n; ++i) {
data[i] = pair<int, int>(nums[i], i);
}
sort(data.begin(), data.end(), greater<pair<int, int> >());
result.resize(n);
SegmentTree segmentTree;
segmentTree.init(n);
for(int i = 0; i < n; ++i) {
result[data[i].second] = segmentTree.query(1, 0, n - 1, 0, data[i].second);
segmentTree.insert(1, 0, n - 1, data[i].second);
}
return result;
}

// Input : 4 3 7 1
// output: 0 1 0 3

Это легко, но не так «очевидно», как другая типичная проблема дерева сегментов. Поможет имитация ручкой и бумагой с произвольным вводом.

Есть и другие O(nlogn) подходит с BST, Fenwick tree и сортировкой слиянием.