algorithm - 一个数据结构问题

Question

给定一个整数序列，有多个查询。每个查询都有一个范围 [l, r]，你要找到给定范围 [l, r] 的中位数

查询数量可大至100,000序列长度最大可达10万

不知道有没有数据结构可以支持这样的查询

---

我的解决方案:

今天咨询了小伙伴，他说用分区树。

我们可以在 nlog(n) 时间内构建一个分区树，并在 log(n) 时间内回答每个查询

划分树其实就是归并排序的过程，只是对于树中的每一个节点，它都保存了到左子树的整数个数。因此，我们可以使用这些信息来处理查询。

这是我的代码:

这个程序是在给定的区间 [l, r] 中找到 x，使下面的方程最小化。

alt text http://acm.tju.edu.cn/toj/3556_01.jpg

解释:

seq保存序列

pos保存排序后的位置

ind 保存索引

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

这称为范围中值查询问题。以下论文可能相关:Towards Optimal Range Medians . (免费链接，感谢 belisarius)。

摘自论文摘要:

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log^2n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)^2) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.

Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.

当然，您可以在 O(n^3) 时间(甚至可能是 O(n^2logn) 时间)和 O(n^2) 空间内对整个数组进行预处理，以便能够在 O( 1)时间。

附加约束可能有助于简化解决方案。例如，我们是否知道 r-l 将小于已知常数？等等……