一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 663|回复: 4
收起左侧

[算法题] 用QuadTree解决Submatrix Sum Query的时间复杂度是多少?

[复制链接] |试试Instant~ |关注本帖
stellari 发表于 2015-7-21 21:12:54 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
很常见的题:

给定一个N x N的矩阵,要求实现set(i, j, newValue)和getSum(i1, j1, i2, j2)。其中set是将[i, j]位置上的元素设为newValue;getSum则是返回[i1, j1] ~ [i2, j2]这个子矩阵中的元素和。set和getSum被调用的频率差不多高。

我的想法是建立一个QuadTree,其中每个节点Ni代表一个子矩阵M,在Ni处储存M中元素和;并且将M等分为4个矩阵,以这4个子矩阵又建立四个子节点。以此类推。求和时,用类似于Segment Tree的思路,把待查询的子矩阵范围分成四个部分,在子节点中分别查询每个部分的和。如果待查询矩阵的某个部分完全覆盖了某个节点所涵盖的矩阵范围,则直接返回和,不需要继续向下查询了。

问题是:上面这种算法在1D情况下,查询一个范围内的和只需O(logN)时间。因为可以证明在每层中最多查询两个节点。但是到了2D情况,这点似乎就不那么容易看出来了。我想了一段时间,还是无法证明这种方法是否能够做到对数时间复杂度。

地里有没有其他同学能提供一个思路?不胜感激。
zhuli19901106 发表于 2015-7-21 21:46:42 | 显示全部楼层
这儿有一题,POJ1195。解法是二维树状数组,可以实现log(N) * log(N)时间的修改和求和。
我以前写的代码,其中树状数组的部分是关键代码:
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. using namespace std;

  5. const int MAXN = 1024;
  6. int c[MAXN + 1][MAXN + 1];
  7. int n;

  8. int low_bit(int x)
  9. {
  10.         return x & (-x);
  11. }

  12. void add_value(int i, int j, int v, int n)
  13. {
  14.         int j1;

  15.         while(i <= n){
  16.                 j1 = j;
  17.                 while(j1 <= n){
  18.                         c[i][j1] += v;
  19.                         j1 += low_bit(j1);
  20.                 }
  21.                 i += low_bit(i);
  22.         }
  23. }

  24. int get_sum(int i, int j)
  25. {
  26.         int j1;
  27.         int sum;

  28.         if(i <= 0 || j <= 0){
  29.                 return 0;
  30.         }

  31.         sum = 0;
  32.         while(i > 0){
  33.                 j1 = j;
  34.                 while(j1 > 0){
  35.                         sum += c[i][j1];
  36.                         j1 -= low_bit(j1);
  37.                 }
  38.                 i -= low_bit(i);
  39.         }

  40.         return sum;
  41. }

  42. int partial_sum(int x1, int y1, int x2, int y2)
  43. {
  44.         return get_sum(x2, y2) + get_sum(x1 - 1, y1 - 1) - get_sum(x2, y1 - 1) - get_sum(x1 - 1, y2);
  45. }

  46. int main()
  47. {
  48.         int op;
  49.         int x1, y1, x2, y2, v;

  50.         memset(c, 0, (MAXN + 1) * (MAXN + 1) * sizeof(int));
  51.         while(scanf("%d", &op) == 1){
  52.                 if(op == 0){
  53.                         scanf("%d", &n);
  54.                 }else if(op == 1){
  55.                         scanf("%d%d%d", &x1, &y1, &v);
  56.                         ++x1;
  57.                         ++y1;
  58.                         add_value(x1, y1, v, n);
  59.                 }else if(op == 2){
  60.                         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  61.                         ++x1;
  62.                         ++y1;
  63.                         ++x2;
  64.                         ++y2;
  65.                         printf("%d\n", partial_sum(x1, y1, x2, y2));
  66.                 }else if(op == 3){
  67.                         break;
  68.                 }
  69.         }

  70.         return 0;
  71. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| stellari 发表于 2015-7-21 22:05:13 | 显示全部楼层
zhuli19901106 发表于 2015-7-21 21:46
这儿有一题,POJ1195。解法是二维树状数组,可以实现log(N) * log(N)时间的修改和求和。
我以前写的代码, ...

多谢提醒!以前对BIT不太了解,这么一看的话,确实比Segment Tree的实现要简单不少啊。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-21 22:07:36 | 显示全部楼层
stellari 发表于 2015-7-21 22:05
多谢提醒!以前对BIT不太了解,这么一看的话,确实比Segment Tree的实现要简单不少啊。

嗯,这东西真心优美,不过适用范围很窄,所以没什么机会用上就是了~~
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-12-14 16:21:04 | 显示全部楼层
本帖最后由 silenceleaf 于 2015-12-14 16:23 编辑

用四叉树是可以解的,时间是log(m*n)。 思路就是把matrix分成四份,每份是一个subtree,一直分到只有一个。然后你getsum就看是在哪个范围内,在这个范围内就加上,不在就return 0。但是在范围内有两种,一种完全包含,一种部分包含。全部包含就把这个node的值加上,部分包含就继续往下分。update更简单,就找应该update的那个branch即可,然后recursion下去直到那个node。
要想知道每个subtree代表的范围,就要在node里面记录 lefttop和rightbottom即可。
其实相当于2d化为1d。
同理如果是三维也适用。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 01:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表