Соответствующая структура данных для добавления и поиска запросов

Question

У меня есть два типа запросов.

1 XY

Добавить элемент X, Y раз в коллекцию.

2 N

Количествозапросы <5 * 10 ^ 5 </p>

X <10 ^ 9 </p>

Y <10 ^ 9 </p>

Найти N-й элемент в отсортированной коллекции.

Iпопытался установить STL, но это не сработало.

Я думаю, что нам нужно сбалансированное дерево с каждым узлом, содержащим два значения данных.

Первым значением будет элемент X. А другим будет префиксная сумма всехY элементов меньше или равно значению.

Когда мы добавляем элемент X, найдите препроцессор этого первого значения. Добавьте второе значение, связанное с препроцессором, к Y.

При поиске N-го элемента. Поиск в дереве (второе значение) значения, непосредственно меньшего, чем N.

Как эффективно реализовать эту структуру данных?

Answer 1

Это легко сделать, используя дерево сегментов структура данных со сложностью O (Q * log (10 ^ 9))

1. Мы должны использовать так называемые "разреженные"дерево сегментов, так что мы создаем узлы только при необходимости, а не все узлы.
2. В каждом узле мы будем сохранять количество элементов в диапазоне [L, R]
3. Теперь добавления некоторого элементаВремя y может быть легко сделано путем обхода дерева сегментов от корня до листа и обновления значений (также создавая узлы, которые еще не существуют). Поскольку высота дерева сегментов является логарифмической, это занимает log N раз, когда N - это начальная длина нашего интервала (10 ^ 9)
4. Поиск k-го элемента можно легко выполнить с помощью бинарного поиска по дереву сегментов, поскольку на каждомВ узле мы знаем количество элементов в некотором диапазоне, мы можем использовать эту информацию для перемещения влево или вправо к элементу, который содержит k-тый

Пример кода (C ++):

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int sz = 31*4*5*100000;
ll seg[sz];
int L[sz],R[sz];
int nxt = 2;

void IncNode(int c, int l, int r, int idx, int val)
{
    if(l==r)
    {
        seg[c]+=val;
        return;
    }

    int m = (l+r)/2;

    if(idx <= m)
    {
        if(!L[c])L[c]=nxt++;
        IncNode(L[c],l,m,idx,val);
    }
    else
    {
        if(!R[c])R[c]=nxt++;
        IncNode(R[c],m+1,r,idx,val);
    }

    seg[c] = seg[L[c]] + seg[R[c]];
}

int FindKth(int c, int l, int r, ll k)
{
    if(l==r)return r;

    int m = (l+r)/2;

    if(seg[L[c]] >= k)return FindKth(L[c],l,m,k);
    return FindKth(R[c],m+1,r,k-seg[L[c]]);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int Q;
    cin>>Q;
    int L = 0, R = 1e9;

    while(Q--)
    {
        int type;
        cin>>type;

        if(type==1)
        {
            int x,y;
            cin>>x>>y;
            IncNode(1,L,R,x,y);
        }
        else
        {
            int k;
            cin>>k;
            cout<<FindKth(1,L,R,k)<<"\n";
        }
    }
}

Answer 2

Ведение суммы префикса в каждом узле нецелесообразно. Это будет означать, что каждый раз, когда вы добавляете новый узел, вы должны обновлять сумму префикса в каждом узле, который следует за ним в дереве. Вместо этого вам нужно поддерживать поддерево суммы: каждый узел должен содержать сумму значений Y для своего собственного ключа и ключей всех потомков. Ведение сумм поддерева при обновлении дерева должно быть простым.

Когда вы отвечаете на запрос типа 2, на каждом узле вы спускаетесь в левое поддерево, если N меньше или равно значению суммы поддерева. S левого ребенка (я предполагаю, что N индексируется 1). В противном случае вычтите S + 1 из N и спуститесь в правое поддерево.

Кстати, если весь набор значений X известен заранее, то вместо сбалансированного BST вы можете использовать дерево диапазонаили двоичное индексированное дерево.