关于线段树套线段树

zhangjinxuan

一个二维平面，支持子矩阵的整体加、乘，和子矩阵最大值、和的查询，怎么用线段树套线段树做？

显然需要使用线段树中懒标记的思想，但是在二维的情况下，怎么正确地使用懒标记？

zhangjinxuan

FishC 发表于 2024-7-5 21:32
哎呀，这个问题可真是有点鱼腩进了深水区的感觉。线段树套线段树，就像是在一棵树上又搭建了一棵树，真是“ ...

可以使用 C++ 语言解决吗？另外这个问题的二维平面大小很大，可以使用动态开点的技巧吗？

zhangjinxuan

FishC 发表于 2024-7-5 21:35
当然可以使用C++来解决这个问题，并且你提到的“动态开点”技巧，对于处理大规模的二维平面问题非常有 ...

You used a loop to update the inner segment tree for each dimension, and this time complexity is not correct.

zhangjinxuan

FishC 发表于 2024-7-5 21:39
你说得非常对，用嵌套的循环来更新内层线段树，时间复杂度会非常高。为了提高效率，我们需要在每层操作 ...

然而你还是用了循环更新每一个维度的内层线段树，这是你 update_x 的实现：

1. if (x1 <= lx && rx <= x2) {
   
2.             for (int i = lx; i <= rx; ++i) { // This time complexity is not correct.
   
3.                 update_y(tree[idx][i], x1, x2, y1, y2, mul, add);
   
4.             }
   
5.             return;
   
6.         }

复制代码

所以有没有对于外层的线段树使用懒标记的技巧？

zhangjinxuan

FishC 发表于 2024-7-5 21:41
你说得对，直接在循环中更新内层线段树确实会导致效率低下。我们需要通过递归来避免这种问题，并充分利 ...

你写了一半就没有写了，是的确没有任何方法了吗，我可以考虑使用其他的方式解决这个问题。

zhangjinxuan

歌者文明清理员 发表于 2024-7-5 21:53
zhangjinxuan使用ai解题了？

我用 ai 做题的话我肯定不会在这里问。