Проблема структуры данных

Question

Учитывая последовательность целых чисел, существует ряд запросов. Каждый запрос имеет диапазон [l, r], и вы должны найти медиану данного диапазона [l, r]

Количество запросов может достигать 100 000 Длина последовательности может достигать 100 000

Интересно, может ли какая-либо структура данных поддерживать такой запрос

---

Мое решение:

Сегодня я консультируюсь со своим партнером, и он говорит использовать дерево разделов.

Мы можем построить дерево разделов за время nlog (n) и ответить на каждый запрос за время log (n)

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

вот мой код:

Эта программа предназначена для поиска x в заданном интервале [l, r], что минимизирует следующее уравнение.

альтернативный текст http://acm.tju.edu.cn/toj/3556_01.jpg

Пояснение:

seq сохраняет последовательность

pos сохраняет позицию после сортировки

Инд сохраняет индекс

cntL сохраняет количество целых чисел, идущих к левому дереву в заданном диапазоне

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100008
typedef long long LL;
int n, m, seq[N], ind[N], pos[N], next[N];
int cntL[20][N];
LL sum[20][N], sumL, subSum[N];

void build(int l, int r, int head, int dep)
{
    if (l == r)
    {
        cntL[dep][l] = cntL[dep][l-1];
        sum[dep][l] = sum[dep][l-1];
        return ;
    }
    int mid = (l+r)>>1;
    int hl = 0, hr = 0, tl = 0, tr = 0;
    for (int i = head, j = l; i != -1; i = next[i], j++)
    {
        cntL[dep][j] = cntL[dep][j-1];
        sum[dep][j] = sum[dep][j-1];
        if (pos[i] <= mid)
        {
            next[tl] = i;
            tl = i;
            if (hl == 0) hl = i;
            cntL[dep][j]++;
            sum[dep][j] += seq[i];
        }
        else
        {
            next[tr] = i;
            tr = i;
            if (hr == 0) hr = i;
        }
    }
    next[tl] = -1;
    next[tr] = -1;
    build(l, mid, hl, dep+1);
    build(mid+1, r, hr, dep+1);
}

int query(int left, int right, int ql, int qr, int kth, int dep)
{
    if (left == right)
    {
        return ind[left];
    }
    int mid = (left+right)>>1;
    if (cntL[dep][qr] - cntL[dep][ql-1] >= kth)
    {
        return query(left, mid, left+cntL[dep][ql-1]-cntL[dep][left-1], left+cntL[dep][qr]-cntL[dep][left-1]-1, kth, dep+1);
    }
    else
    {
        sumL += sum[dep][qr]-sum[dep][ql-1];
        return query(mid+1, right, mid+1+ql-left-(cntL[dep][ql-1]-cntL[dep][left-1]), mid+qr+1-left-(cntL[dep][qr]-cntL[dep][left-1]), \
                kth-(cntL[dep][qr]-cntL[dep][ql-1]), dep+1);
    }
}

inline int cmp(int x, int y)
{
    return seq[x] < seq[y];
}

int main()
{
    int ca, t, i, j, middle, ql, qr, id, tot;
    LL ans;
    scanf("%d", &ca);
    for (t = 1; t <= ca; t++)
    {
        scanf("%d", &n);
        subSum[0] = 0;
        for (i = 1; i <= n; i++) 
        {
            scanf("%d", seq+i);
            ind[i] = i;
            subSum[i] = subSum[i-1]+seq[i];
        }
        sort(ind+1, ind+1+n, cmp);
        for (i = 1; i <= n; i++)
        {
            pos[ind[i]] = i;
            next[i] = i+1;
        }
        next[n] = -1;
        build(1, n, 1, 0);
        printf("Case #%d:\n", t);
        scanf("%d", &m);
        while (m--)
        {
            scanf("%d%d", &ql, &qr);
            ql++, qr++;
            middle = (qr-ql+2)/2;
            sumL= 0;
            id = query(1, n, ql, qr, middle, 0);
            ans = subSum[qr]-subSum[ql-1]-sumL;
            tot = qr-ql+1;
            ans = ans-(tot-middle+1)*1ll*seq[id]+(middle-1)*1ll*seq[id]-sumL;
            printf("%lld\n", ans);
        }
        puts("");
    }
}

Answer 1

Это называется проблемой Range Median Query. Может быть полезен следующий документ: На пути к медианам оптимального диапазона . (Бесплатная ссылка, спасибо Велисарию).

Из тезисов доклада:

Рассмотрим следующую проблему: Учитывая несортированный массив из n элементов, и последовательность интервалов в массив, вычислить медиану в каждом из подмассивы, определяемые интервалы. Опишем простой алгоритм который требует O (nlogk + klogn) время ответить на k таких медианных запросов. Это улучшает предыдущие алгоритмы логарифмический фактор и соответствует нижняя оценка сравнения для k = O (n). Пространство сложности нашего простого Алгоритм O (nlogn) в указателе модель машины и O (n) в оперативной памяти модель. В последней модели более вовлеченная O (n) структура данных пространства может быть построено за O (nlogn) время где время на запрос сокращается до O (LOGN / loglogn). Мы также даем эффективные динамические варианты обоих структуры данных, достигающие O (log ^ 2n) время запроса, используя пространство O (nlogn) в модель сравнения и O ((logn / loglogn) ^ 2) время запроса с использованием O (nlogn / loglogn) место в оперативной памяти модель, и показать, что в клетке-зонде модель, любая структура данных, которая поддерживает обновления за O (log ^ O (1) n) раз должно иметь время запроса Ω (logn / loglogn).

Наш подход естественным образом обобщает больший диапазон измерений проблемы, где позиции элементов и диапазоны запросов многомерны - это уменьшает средний диапазон запроса до логарифмическое число отсчета диапазона запросы.

Конечно, вы можете предварительно обработать весь массив за O (n ^ 3) времени (или, возможно, даже за O (n ^ 2logn) времени) и за O (n ^ 2), чтобы иметь возможность вернуть медиану в O ( 1) время.

Дополнительные ограничения могут помочь упростить решение. Например, знаем ли мы, что r-l будет меньше известной константы? и т.д ...