Как построить treap по неявному ключу из массива?

Покопался в сети, на вики нашел решение за O(n), но я не понял как поддерживать количество элементов в вершинах дерева. После построения обходить дерево не хотелось в итоге родилось вот это вот:

    treap_array(const _list<int>& __d) {
      using T = pair<pnode, int>;
      stack<T, _list<T>> s;
      for (auto x : __d) {
        int p = rnd.rand();
        auto lst = null;
        int sum = 0;
        while (s.size() > 0 and s.top().first->priority < p) {
          auto [last, sz] = s.top();
          s.pop();
          sum += sz;
          last->size += sum;
          lst = last;
        }
        auto n = new node{0, p, x, lst, null};
        n->size = lst->size;
        if (s.size() > 0) {
          s.top().first->right = n;
          s.top().second += sum;
        }
        else
          root = n;
        s.push({n, 1});
      }
      int sum = 0;
      while (s.size() > 0) {
        auto [n, sz] = s.top();
        s.pop();
        sum += sz;
        n->size += sum;
      }
    }

Можно ли так? Что можно улучшить? Или кодинг не для меня?