[DataStructure]Quad Tree

QuadTree是一种应用在2D数据当中把空间递归地四等分的数据结构。在图像处理当中有很多的应用，除此之外其在range query当中也可以给我提供帮助。对于给定的Matrix，我们可以递归地将其四等分，如下图所示(picture from StackOverflow)：

QuadTree Node:

	struct Node
	{
	int sum = 0;
	Node* children[4] = {nullptr, nullptr, nullptr, nullptr};
	Node(int val) : sum(val)
	{
	}
	}

view raw quadtree_node.cpp hosted with ❤ by GitHub

我们在这里以Region Sum为例，假设输入Matrix为m * n。首先我们要构建QuadTree，这和给定array建Binary Tree是类似的，Bottom-up建造即可。O(m * n)时间，代码如下：

	Node* createTree(vector<vector<int>>& matrix, int row1, int row2, int col1, int col2)
	{
	if(row1 > row2 || col1 > col2)return nullptr;
	if(row1 == row2 && col1 == col2)return new Node(matrix[row1][col1]);
	int rMid = row1 + (row2 - row1) / 2, cMid = col1 + (col2 - col1) / 2;
	auto topL = createTree(matrix, row1, rMid, col1, cMid);
	auto topR = createTree(matrix, row1, rMid, cMid + 1, col2);
	auto botL = createTree(matrix, rMid + 1, row2, col1, cMid);
	auto botR = createTree(matrix, rMid + 1, row2, cMid + 1, col2);
	Node* node = new Node(val(topL) + val(topR) + val(botL) + val(botR));
	node->children[0] = topL;
	node->children[1] = topR;
	node->children[2] = botL;
	node->children[3] = botR;
	return node;
	}

view raw quadtree_create.cpp hosted with ❤ by GitHub

对于查询来说，分三种情况：

• 区间如果不满足左边界小于等于右边界，上边界小于等于下边界的基本条件，return 0。这是base case
• 如果查询区间和当前区间没有交集，return 0。
• 如果有，递归地查询四个子区间。

代码如下：

	int query(Node* curr, int row1, int row2, int col1, int col2, int qRow1, int qRow2, int qCol1, int qCol2)
	{
	if (row1 > row2 || col1 > col2)return 0;
	if(qRow1 > row2 || qRow2 < row1 || qCol1 > col2 || qCol2 < col1)return 0;
	if(qRow1 <= row1 && qCol1 <= col1 && qRow2 >= row2 && qCol2 >= col2)return curr->sum;
	int rMid = row1 + (row2 - row1) / 2, cMid = col1 + (col2 - col1) / 2;
	int res = query(curr->children[0], row1, rMid, col1, cMid, qRow1, qRow2, qCol1, qCol2);
	res += query(curr->children[1], row1, rMid, cMid + 1, col2, qRow1, qRow2, qCol1, qCol2);
	res += query(curr->children[2], rMid + 1, row2, col1, cMid, qRow1, qRow2, qCol1, qCol2);
	res += query(curr->children[3], rMid + 1, row2, cMid + 1, col2, qRow1, qRow2, qCol1, qCol2);
	return res;
	}

view raw quadtree_query.cpp hosted with ❤ by GitHub

时间复杂度的话，取决于查询区间的范围，最好的情况查询区间正好和当前区间重合，O(1)。最坏的情况对于每个分区我们可能要一直查询到底，时间复杂度O(m * n)，比如下图例子：

更新的话，我们只要看更新的元素在四个子节点其中的哪个，然后递归地进行更新即可。时间复杂度O(log(m * n))，这里我们不考虑频繁的区间更新，如果需要支持高频的区间更新的话可以考虑Segment Tree，因为显然Segment Tree的区间更新更有效率。代码如下：

	int update(Node* curr, int row1, int row2, int col1, int col2, int row, int col, int val)
	{
	if(row1 == row2 && col1 == col2)
	{
	int add = val - curr->sum;
	curr->sum += add;
	return add;
	}
	int add = 0, rMid = row1 + (row2 - row1) / 2, cMid = col1 + (col2 - col1) / 2;
	if(row <= rMid && col <= cMid)add = update(curr->children[0], row1, rMid, col1, cMid, row, col, val);
	else if(row <= rMid && col > cMid)add = update(curr->children[1], row1, rMid, cMid + 1, col2, row, col, val);
	else if(row > rMid && col <= cMid)add = update(curr->children[2], rMid + 1, row2, col1, cMid, row, col, val);
	else add = update(curr->children[3], rMid + 1, row2, cMid + 1, col2, row, col, val);
	curr->sum += add;
	return add;
	}

view raw quadtree_update.cpp hosted with ❤ by GitHub

QuadTree所占用的空间为O(m * n)，因为其一定有m * n个叶节点，并且internal节点的数量不会啊超过叶节点的数量。