Witam,

od pewnego czasu nurtuje mnie tytułowe pytanie: "Ile elementów
w zadanym zbiorze jest mniejszych od wybranego elementu?"

Dla dość specyficznej relacji częsciowego porządku szukam
efektywnej struktury/algorytmu, która ułatwi mi odpowiedź na to
pytanie.

O to charakterystyka zbioru:

- Zbiór unikalnych elementów E={e[i],i=1...N} o liczności rzędu 10^6

- Każdy element posiada pewną liczbę cech (obiekty mają rożne
ilości cech), oznaczmy to e[i]={e[i,j],j=1...n_i}, średnia
liczność cech w zbior E wynosi około 30-50, tzn.:
sum_i #e[i] ~= 50*#E

- Każda cecha e[i,j] jest uporządkowawaną parą liczb dodatnich:
e[i,j] = ( e[i,j,1], e[i,j,2] ), gdzie e[i,j,1] <= e[i,j,2].
(równość zachodzi co najwyżej dla jednej cechy w elemencie)

- Relacja częściowego porządku cech:

e[i1,j1] < e[i2,j2] <==>
(e[i1,j1,1] < e[i2,j2,1]) & (e[i1,j1,2] < e[i2,j2,2])

Każda cecha (czyli para liczbowa) jest unikalna w całym
zbiorze E, więc relacja e[i1,j1] = e[i2,j2] zachodzi tylko
gdy i1=i2 i j1=j2. Nie wszystkie cechy są porównywalne wg
powyższej definicji. W dodatku *żadne* dwie cechy danego
elementu nie są porównywalne.

- Na koniec właściwa relacja porządkująca elementy e[i]:

e[i1] < e[i2] <==>
istnieje choć jedna para j1,j2: e[i1,j1] < e[i2,j2]

Definicja jest jednoznaczna/niesprzeczna, tzn. jeżeli
dla danych i1,i2 istnieją powyższe j1,j2, to nie istnieją
k1, k2 takie, że zachodzi relacja odwrotna e[i1,k1] > e[i2,k2].

Nie wiem czy to istotne, ale zbiór e[i] jest już zanurzony w
liniowy porządkek, tzn. jeżeli zachodzi e[i1] < e[i2], to
i1<i2.

Czy istnieje jakieś rozwiązanie o złożonościach
- przygotowanie danych: O(sum #e[i])
- pojedyńcze pytanie O(#e[i])

Czekam na pomysły, literaturę, ...

Pozdrawiam, Mirek.