Cod sursa(job #3313021)

Utilizator ionicaion ionica Data 1 octombrie 2025 19:17:01
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb

#include <iostream>
#define NM 100005
using namespace std;

int aib[100], n;

void adauga(int poz,int val)
{
    int x,p;
    x=poz;
    do{
        aib[x]=aib[x]+val;
        p=x&(-x);
        x=x+p;
    }while(x<=n);
}

int Query(int poz)
{
    int s,x,p;
    s = 0;
    x=poz;
    while(x>0)
    {
        s=s+aib[x];
        p=x&(-x);
        x=x-p;
    }
    return s;
}

int main()
{
    int i, a;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> a;
        cout << Query(a - 1) << " ";
        adauga(a,1);
    }
    return 0;
}
/**
15
11 5 8 14 10 2 4 13 1 7 3 9 15 6 12
**/