Как использовать двоичное индексированное дерево для подсчета количества элементов, которое меньше значения в индексе?

Question

Проблема состоит в том, чтобы посчитать количество значений меньше значения после индекса. Вот код, но я не могу понять, как двоичное индексированное дерево было использовано для этого?

#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;


}

Было бы полезно, если бы кто-то мог объяснить рабочий принцип кода.

Answer 1

Чтобы понять BIT, это одна из лучших ссылок.
TC дает полное объяснение функций, которые вы использовали, но остальная часть - логика того, как его использовать.
Для базового понимания:

Задача: есть n куч, и в каждой куче изначально есть 1 камень, затем мы добавляем камни от u к v… найдите, сколько камней в данной куче.

решение с ответом на каждой итерации: http://pastebin.com/9QJ589VR. После того, как вы это поймете, попробуйте реализовать свой вопрос.

Answer 2

Я погуглил BIT для чайников и нашел это https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

Основная идея - изолировать последний бит. во время запроса мы идем вниз по массиву, а во время обновления мы идем вверх по массиву.

например, запрос (6) будет добавлять сумму в BIT[6], но также добавить сумму в BIT [4] и BIT [0], потому что 6(110) - 2 = 4(100) - 4 = 0.

          public static void update(int x, int val, int size){
        //int k =x;
        x++;
        for (; x<size; x+= x&(-x))
            BIT[x]+=val;
    }
    public static int query(int x){
        //int k =x;
        int toreturn =0;
        for (; x >0; x-= x&(-x)) 
            toreturn+=BIT[x];
        return toreturn;
    }
    public static List<Integer> countSmaller(int[] nums) {
        // will only  work for positive numbers less that 7. 
        int size = 7;
        BIT = new int[size];
        List<Integer> result = new ArrayList<Integer>();

        for (int i =nums.length-1; i >=0; i--) {
            int smaller_count = query(nums[i]);
            result.add(smaller_count);
            update(nums[i], 1, size);
        }
        Collections.reverse(result);
        return result;
    }