Drzewo potęgowe

Cześć,
Przepisałem z książki (25 lat OI) znak w znak implementację drzewa potęgowego i niestety nie działa ona poprawnie. Funkcja nth(i) powinna zwracać wartość i-tego co do wartości elementu w drzewie, zakładając że i należy do zakresu od 1 do n. Funkcja zwraca wartości niepoprawne. Proszę o pomoc w zdiagnozowaniu problemu, bo nie do końca rozumiem jak ten kod miałby działać, więc tym bardziej nie umiem go naprawić.
Kod:
https://4programmers.net/Pastebin/15078

#include <iostream>
using namespace std;

const int MAX_N = 1000000;
int tree[MAX_N];
int n,N;

int pot(int x)
{
	return x & -x;
}

void update(int x, int cnt)
{
	while(x <= n)
	{
		tree[x] += cnt;
		x += pot(x);
	}
}

int beforeeq(int x)
{
	int sum = 0;
	while(x > 0)
	{
		sum += tree[x];
		x -= pot(x);
	}
	return sum;
}

int nth(int i)
{
	int x = 0, l = N;
	while(l > 0)
	{
		if(x + l <= n && tree[x+l] < i)
		{
			i -= tree[x+l];
			x += l;
		}
		l /= 2;
	}
	return x+1;
}

int main() {
	cin >> n;
	int x;
	for(int i = 0; i < n; ++i)
	{
		cin >> x;
		update(x, 1);
	}
	N = 1;
	while(N < n)
	{
		N *= 2;
	}
	
	for(int i = 1; i <= n; ++i)
	{
		cout << nth(i) << ' ';
	}
	return 0;
}

Dla wejścia:
10 1 90 5 3 2 1 23 68 12 102
Wyjście wygląda tak:
1 1 2 3 5 11 11 11 11 11

To sie robi w jednej linijce:
http://miwo.wikidot.com/drzewo-potegowe

vpiotr napisał(a):

To sie robi w jednej linijce:
http://miwo.wikidot.com/drzewo-potegowe

Ta implementacja nie zawiera w ogóle funkcji nth(...). To co jest w tej implementacji, działa w mojej. Zależy mi właśnie na tej konkretnej funkcji.

Przecież tamta funkcja read, to jest właśnie nth!

Nie wiem czy czegoś fundamentalnie nie rozumiem, ale moim zdaniem funkcja read to odpowiednik mojego beforeeq. Gdyby to była funkcja nth, to wywołanie read(1) powinno zwrócić minimum ze zbioru, a read(n) maksimum, a tak nie jest:
https://ideone.com/0MpBsT