0
Задача состоит в том, чтобы подсчитать количество значений, меньшее значения после индекса. Вот код, но я не могу понять, как было использовано двоичное индексированное дерево для этого?Как использовать двоичное индексированное дерево для подсчета количества элементов, которое меньше значения по индексу?
#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
#define MOD 1000000007
#define MAXN 10
using namespace std;
typedef pair<int, int> ii;
int BIT[MAXN+1];
int a[MAXN+1];
vector<ii> temp;
int countSmallerRight[MAXN+1];
int read(int idx) {
int sum = 0;
while (idx > 0) {
sum += BIT[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(int idx, int val) {
while (idx <= MAXN) {
BIT[idx] += val;
idx += (idx & -idx);
}
}
int main(int argc, const char * argv[])
{
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &a[i]);
temp.push_back(ii(a[i], i));
}
sort(temp.begin(), temp.end());
countSmallerRight[temp[0].second] = 0;
update(1, 1);
update(temp[0].second, -1);
for (int i = 1; i < N; i++) {
countSmallerRight[temp[i].second] = read(temp[i].second);
update(1, 1);
update(temp[i].second, -1);
}
for (int i = 1; i <= N; i++) {
printf("%d,", countSmallerRight[i]);
}
putchar('\n');
return 0;
}
Было бы полезно, если бы кто-нибудь мог объяснить действующего принципала кода.
Если вы поставили бы задачу понятным образом, это было бы еще более полезно. Что такое ценности? Что такое индекс? Что такое «значение после индекса»? ... Кто меньше стоимости? Количество элементов? Или значения элементов, которые мы подсчитываем? Вы написали первый. – Gangnus