📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2223| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

用QuadTree解决Submatrix Sum Query的时间复杂度是多少?

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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情况,这点似乎就不那么容易看出来了。我想了一段时间,还是无法证明这种方法是否能够做到对数时间复杂度。

地里有没有其他同学能提供一个思路?不胜感激。

上一篇:第82道题,删除链表里重复节点(只要重复,一个都不保留)
下一篇:Help - check for empty array
🔗
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。
同理如果是三维也适用。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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