Dlaczego mój program jest taki wolny ? [Zadanie z użyciem drzewa przedziałowego]

Question

Na wejściu dostajemy n i m (0 < n, m <= 500 000), n to dlugosc ciagu liczb na wejściu które dostajemy, m to ilość zapytań. Mamy powiedzieć jaki jest nadłuższy rosnący podciąg podanego ciągu, poźniej jest m zmian w postaci p, v gdzie p to komórka w ciagu która zmienia swoją wartość na v, i dla każdego zapytania też mamy podać najdłuższy rosnący podciąg. Mam drzewo przedziałowe i kod działający w O(log(n) * m) [Według mojej wiedzy]:

#include <bits/stdc++.h>

using namespace std;

long long next_pow_of_2(int num){
    int pow_of_2 = 2;
    while (pow_of_2 < num)
        pow_of_2 *= 2;
    return pow_of_2;
}

class Segment{
public:
    int beg;
    int end;
    int mid;
    int max = 1;
    int l = 0;
    int r = 0;
};

class SegmentTree{
public:
    vector<Segment> tree;
    int size;

    void update_leaves(){
        for (int i = 0; i < size; i++){
            tree[i + size].beg = tree[i + size].end = tree[i + size].mid = i;
            tree[i + size].l = tree[i + size].r = 1;
        }
    }

    void compare(int j, vector<int>& tab){
        if (tree[j * 2 + 1].beg >= (int)tab.size() || tab[tree[j * 2].end] >= tab[tree[j * 2 + 1].beg]){
            tree[j].l = tree[j * 2].l;
            tree[j].r = tree[j*2+1].r;

            tree[j].max = max(tree[j * 2].max, tree[j*2+1].max);
        }
        else{
            if (tree[j * 2].l == tree[j * 2].end - tree[j * 2].beg + 1 &&
                tree[j*2+1].r == tree[j*2+1].end - tree[j*2+1].beg + 1){
                    tree[j].l = tree[j].r = tree[j * 2].l + tree[j*2+1].r;
            }
            else if (tree[j * 2].l == tree[j * 2].end - tree[j * 2].beg + 1){
                tree[j].l = tree[j * 2].l + tree[j*2+1].l;
                tree[j].r = tree[j*2+1].r;
            }
            else if (tree[j*2+1].r == tree[j*2+1].end - tree[j*2+1].beg + 1){
                tree[j].r = tree[j * 2].r + tree[j*2+1].r;
                tree[j].l = tree[j * 2].l;
            }
            else{
                tree[j].l = tree[j * 2].l;
                tree[j].r = tree[j*2+1].r;
            }
            tree[j].max = max(tree[j * 2].r + tree[j*2+1].l, max(tree[j * 2].max, max(tree[j*2+1].max, max(tree[j].l, tree[j].r))));
        }
    }

    void update_vertex(vector<int>& tab){
        for (int i = size / 2; i > 0; i /= 2){
            for (int j = i; j < i * 2; j++){
                tree[j].beg = tree[j * 2].beg;
                tree[j].end = tree[j * 2 + 1].end;
                tree[j].mid = (tree[j].beg + tree[j].end) / 2;
                compare(j, tab);
            }
        }
    }

    SegmentTree(int n, vector<int>& tab){
        size = next_pow_of_2(n);
        tree.resize(size * 2);
        update_leaves();
        update_vertex(tab);
    }

    void update(int p, vector<int>& tab){
        p = (p + size) / 2;
        while (p >= 1){
            compare(p, tab);
            p /= 2;
        }
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;
    vector<int> tab(n);
    for (int i = 0; i < n; i++){
        cin >> tab[i];
    }
    SegmentTree seg_tree(n, tab);
    cout << seg_tree.tree[1].max << "\n";

    int m, p, v;
    cin >> m;
    for (int i = 0; i < m; i++){
        cin >> p >> v;
        p--;
        tab[p] = v;
        seg_tree.update(p, tab);
        cout << seg_tree.tree[1].max << "\n";
    }

    return 0;
}

Gdy sprawdzam tutaj moje rozwiązanie:
https://szkopul.edu.pl/c/archiwum-zadan-k0mpend1x/submit/

To sprawdzarka mówi że mój program ostatni test wykonuje aż 1.11s! Dlaczego sprawdzarka pokazuje taki czas ?

EDIT:
Może być tak że testy są stare a szkopuł zmienił system oceniania (bierze połowe możliwego czasu jako wzorcówka), tylko to dalej nie wyjaśnia dlaczego to jest aż 1.11s

Answer 1

No co tu się dziwić ?
Wykonujesz operację w pętli : wrzucając do środka funkcję :
- w funkcji nie dość że masz kolejną pętle while,  a w niej kolejną funkcję tym razem... compare która zawiera obliczenia matematyczne liczenia maxymalnej wartości z liczb calkowitych ( bo pracujesz na intach ), do tego wszystkiego w momencie tworzenia obiektu przez konstruktor wywołujesz  gorzej być nie może. wywołujesz kaskadę złożoności obliczeniowej 
 

   size = next_pow_of_2(n);
        tree.resize(size * 2);
        update_leaves();
        update_vertex(tab);

)

Comments

Jak to poprawić? Czy jest różnica jeśli nie wykonam tego w konstruktorze tylko potem?

---

Przecież dane muszę pobrać w pętli, wtedy wykonuje while, ale wykonam go log2(zmienna) razy

---

Nie widzę czemu akurat zacytowany kawałek kodu mógłby być problemem. `next_pow_of_2` wywołuje się raz na cały program i jest trywialnie szybkie.