/*
    Indexelt bináris keresőfa (order-statistics tree, indexed BST)

    Mire jó?
    -----------
    Ez egy sima bináris keresőfa (BST), ahol minden csúcsban tároljuk, hogy a részfája hány elemet tartalmaz (meret).
    Ennek segítségével képesek vagyunk sorszám (index) alapján is lekérni a "k-adik legkisebb" elemet,
    azaz *in-order* sorrend szerinti indexeléssel, O(log n) időben (ha a fa kiegyensúlyozott).

    Miért találták ki?
    ------------------
    - Ha egyszerre kell tudnunk gyorsan keresni, beszúrni/törölni, és az elemek *in-order* indexét is elérni (pl. rangsorolt adatoknál, leaderbord, dinamikus median keresés, stb).
    - Az STL set/map NEM tud indexalapú elérést! Ott csak sorrendi iterálás van, nincs index.

    Hol használják?
    -----------------
    - Online statisztikák, dinamikus median keresés, játékrangsor, versenyalgoritmusok, adatbázis implementációk.

    Miben más, mint az STL set/map?
    ---------------------------------
    - STL-ben nincs indexalapú lekérdezés. Nem tudod megmondani például: "Ki a 10. legkisebb elem a set-ben?".
    - Itt minden beszúrás/törlés után frissítjük a meret-ot, így O(log n) az indexelés (feltéve hogy a fa kiegyensúlyozott – most nincs balanszolás).

    Megjegyzés: ez a példa nem kiegyensúlyozott fa (AVL/Red-Black nélkül), így extrém esetben lehet lassú!
*/

#include <iostream>
#include <stdexcept>

using namespace std;

struct Node {

    int ertek;
    int meret;        // Aktuális részfa mérete (gyermekekkel együtt)

    Node* bal;
    Node* jobb;

    Node(int v) : ertek(v), meret(1), bal(nullptr), jobb(nullptr) {}
};

struct IndexeltBKF {

    Node* gyoker = nullptr;

    // Segédfüggvény a méretek frissítésére minden módosítás után
    void meret_frissites(Node* csomo) {

        if (!csomo) return;

        csomo->meret = 1;

        if (csomo->bal)  
            csomo->meret += csomo->bal->meret;                           // Ha van bal gyermek, akkor a bal részfa méretét hozzáadjuk.
        if (csomo->jobb) 
            csomo->meret += csomo->jobb->meret;                          // Ha van jobb gyermek, akkor a jobb részfa méretét is hozzáadjuk.
    }

    // Beszúrás érték alapján (sima BST logika)
    Node* beszur(Node* csomo, int ertek) {

        if (!csomo) return new Node(ertek);                              // Ha az aktuálisan vizsgált hely (csomo) üres (nullptr), akkor létrehozunk egy új csomópontot 

        if (ertek < csomo->ertek)                                        // Ha a beszúrandó érték kisebb, mint az aktuális csomópont értéke, a beszúrást bal oldalra folytatjuk
            csomo->bal = beszur(csomo->bal, ertek);
        else                                                             // Ha a beszúrandó érték nagyobb vagy egyenlő, a beszúrást jobb oldalra folytatjuk ugyanígy rekurzívan
            csomo->jobb = beszur(csomo->jobb, ertek);

        meret_frissites(csomo);                                          // Miután a rekurzív beszúrás befejeződött, frissítjük az aktuális csomo részfa méretét.

        return csomo;                                                    // Mindig visszaadjuk a (lehet, hogy módosult) aktuális csomópont pointerét a hívónak.
                                                                         // Ez azért kell, hogy a rekurzió során a szülő megfelelően frissítse a bal vagy jobb mutatóját.
    }

    // Felhasználói függvény
    void beszur(int ertek) {                                             // Ez a függvény egy egyszerű publikus "belépési pont" a bináris keresőfa beszúrási műveletéhez.
        gyoker = beszur(gyoker, ertek);                                  // Azért van külön, hogy a felhasználónak ne kelljen tudnia a rekurzív, belső beszur(Node*, int) működéséről és a gyoker kezeléséről.
    }

    // K-adik legkisebb elem visszaadása in-order index alapján (0-alapú!)
    Node* k_adik_legkisebb(Node* csomo, int k) const {

        if (!csomo) return nullptr;                                      // Ha a kapott csomo nullptr, az azt jelenti, hogy elértünk egy üres részfát, 
                                                                         // de a keresett index már nem található — nincs ilyen k-adik elem.
        int balmeret = csomo->bal ? csomo->bal->meret : 0;               // Ha van bal gyermek (csomo->bal), akkor a meret mezője megmondja, hány elem tartozik hozzá.
                                                                         // Ha nincs bal gyermek, akkor 0.
        if (k < balmeret)                                                // Ha a keresett index kisebb, mint a bal részfa mérete, azt jelenti, hogy a keresett k-adik elem a bal részfában van.
            return k_adik_legkisebb(csomo->bal, k);                      // Rekurzívan meghívjuk magunkat a bal gyermekre, ugyanezzel a k-val.

        if (k == balmeret)                                               // Ha k pontosan megegyezik a bal részfa méretével:
            return csomo;                                                // Ez azt jelenti, hogy az in-order sorrendben éppen az aktuális csomópont a k-adik elem.

        return k_adik_legkisebb(csomo->jobb, k - balmeret - 1);          // Ha a fenti két eset egyike sem igaz, a keresett elem a jobb részfában van.
    }                                                                    // Ekkor újra meghívjuk magunkat a jobb gyermekre.


    int k_adik_legkisebb(int k) const {

        Node* n = k_adik_legkisebb(gyoker, k);
        if (n) return n->ertek;
        throw out_of_range("k túl nagy!");
    }

    // In-order bejárás (rendezett kiíratás)
    void kiiratas(Node* csomo) const {

        if (!csomo) return;

        kiiratas(csomo->bal);

        cout << csomo->ertek << " ";

        kiiratas(csomo->jobb);
    }

    void kiiratas() const {

        kiiratas(gyoker);
        cout << '\n';
    }
};