范围搜索（kDTree）

范围搜索是从拥有多个属性的报表集合中，寻找具有特定属性且位于指定范围内的元素，这类问题被称为范围搜索。

我们在这里要解决的是二维的范围搜索问题。

在二维平面上给出一堆点，然后给出n个矩形框。要求输出在矩形框内的所有点的id。

kDtree其实就类似于二叉搜索树（嗯其实差不多就是二叉搜索树）。

题目是 DSL_2_C

我们需要建立2DTree，那就需要对x轴和y轴分别进行排序。实现方式就是，深度为偶数的时候以x轴为基准，深度为奇数时，以y轴为基准。

其实这就是二维分割，可以看作是把对一块大的平面区域进行分割，分别按照x轴和y轴来切一刀，接着对于每个小区域都执行相同的分割。所有的点都在分割边上的时候，停止分割。分割其实就是建立了一个类似于二叉搜索树的东西。

上代码！

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 500005

struct node
{
    int parent, left, right;
    int location; //对应point数组里面的元素的下标
};

class point
{
public:
    int id, x, y;
    point() {}
    point(int id, int x, int y)
    {
        (*this).id = id;
        (*this).x = x;
        (*this).y = y;
    }

    bool operator<(const point &p) const
    {
        return id < p.id;
    }

    void print()
    {
        printf("%d\n", id);
    }
};

int n;
point p[MAXN];
node nd[MAXN];
int node_counter = 0;
const int NIL = -1;

bool cmpX(const point &a, const point &b)
{
    return a.x < b.x;
}

bool cmpY(const point &a, const point &b)
{
    return a.y < b.y;
}

int make2Dtree(int left, int right, int depth)
{
    if (left >= right)
        return NIL;

    int t = node_counter++;

    if (depth % 2 == 0) //以x为基准对p升序排序
    {
        sort(p + left, p + right, cmpX);
    }
    else
    {
        sort(p + left, p + right, cmpY);
    }

    int mid = (left + right) / 2;

    nd[t].location = mid;
    nd[t].left = make2Dtree(left, mid, depth + 1);
    nd[t].right = make2Dtree(mid + 1, right, depth + 1);

    return t;
}

vector<point> ans;

void search(int u, const int &sx, const int &tx, const int &sy, const int &ty, int depth)
{
    int x = p[nd[u].location].x;
    int y = p[nd[u].location].y;

    if (x >= sx && x <= tx && y >= sy && y <= ty)
    {
        ans.push_back(p[nd[u].location]);
    }

    if (depth % 2 == 0)
    {
        if (nd[u].left != NIL)
        {
            if (sx <= x)
                search(nd[u].left, sx, tx, sy, ty, depth + 1);
        }
        if (nd[u].right != NIL)
            if (x <= tx)
                search(nd[u].right, sx, tx, sy, ty, depth + 1);
    }
    else
    {
        if (nd[u].left != NIL)
            if (sy <= y)
                search(nd[u].left, sx, tx, sy, ty, depth + 1);

        if (nd[u].right != NIL)
            if (y <= ty)
                search(nd[u].right, sx, tx, sy, ty, depth + 1);
    }
}

int main()
{
    scanf("%d", &n);

    int x, y;

    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        p[i] = point(i, x, y);
        nd[i].left = nd[i].right = nd[i].parent = NIL;
    }

    int root = make2Dtree(0, n, 0);

    int q;
    scanf("%d", &q);

    int sx, tx, sy, ty;
    for (int i = 0; i < q; ++i)
    {
        ans.clear();
        scanf("%d%d%d%d", &sx, &tx, &sy, &ty);
        search(root, sx, tx, sy, ty, 0);
        sort(ans.begin(), ans.end());

        for (point tmp : ans)
            tmp.print();
        //for(int i=0;i<ans.size();i++)
        //  ans[i].print();

        printf("\n");
    }
}

转载请注明原文链接：https://www.longjin666.top/?p=752

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~