超冷门数据结构——二维线段树详解

NightTide

2022-10-23 16:20:58

Algo. & Theory

编者注：本文为作者远古作品，存在一些谬误。作者已意识到这篇文章的错误但作者已 AFO 且高三无暇更新，希望各位不要进行人身攻击。本人将尽量对本文做出修正。

Lesson 0 - 起因

在很久很久以前，有一个少年，他出了一个题目。

这个题目需要一棵非常非常奇特的树，叫做二维线段树。

但是他翻遍了所有的商场，都没有找到这棵树的种子和育苗手册。

于是他只好自力更生，经过七七四十九天，终于培育出了这棵树。

本着共产主义的原则，他决定将它发扬光大。

好吧其实是我自己出的题目自己不会做然后还找不到什么像样的教程就手推了一遍，为了以后要学二维线段树的人方便写了这篇博客。希望对大家有帮助。

Lesson 1 - 简介

我们在日常水刷题的时候，经常会用到线段树这种数据结构来维护带修改的区间问题，比如：

洛谷 P3373 【模板】线段树 2

如题，已知一个数列，你需要进行下面三种操作：

将某区间每一个数乘上 x

将某区间每一个数加上 x

求出某区间每一个数的和

这类问题用线段树维护起来宗室非常方便，然而，~~生活并不是一条直线，~~在 OI 中，我们并不仅仅是处理一些线性的区间问题，有时候，题目会要求我们处理一些二维的区间问题。比如：

洛谷 P4514 上帝造题的七分钟

如题，有一个初始全为 0 的 n \times m 的矩阵，你需要进行下面两种操作：

L a b c d delta 将 (a,b),(c,d) 为顶点的矩形区域内的所有数字加上 delta。

k a b c d 求 (a,b),(c,d) 为顶点的矩形区域内所有数字的和。

我们想念线段树的功绩，还是希望能够用线段树来处理这些问题，于是乎，二维线段树应运而生。

但是它非常的冷门。冷门到什么程度呢？冷门到连 OI-wiki 上都只简略介绍了它的其中一种写法，总字数不会超过 400 字。

然而它并非没用，所以我将在这篇博客里详细介绍它。

二维线段树是一类算法竞赛中不常用的用来维护二维平面上的一个矩阵中的信息（如矩阵和，矩阵最大值）的数据结构。主流的二维线段树有两种写法：

四叉树写法
树套树写法

两种写法的时间复杂度理论上都是 O(n\log^2 n) 的。（编者注：四分树的理论复杂度就是其最坏复杂度 O(n^2)，O(n\log^2 n) 只能认为是其随机数据下的预估复杂度。而且也只是预估，因为随机数据下的四分树期望复杂度目前没有找到严格证明。）其中，第一种写法用途更加广泛，也更好理解，然而其时间复杂度经常假到 O(n^2) 及以上，（编者注：不是经常假到 O(n^2)，这就是它的正确复杂度。） 同时还具有大肠数，因而实际时间复杂度远远超过理论复杂度，（编者注：这句话完全是错的。） 跑起来的效果不堪入目；较为流行的是第二种写法，然而其用途又存在有限制。一般来讲，如果能够使用树套树的场合，请务必使用树套树写法；如果不行~~我建议你在推一推别的算法~~，在选择使用四叉树。

Lesson 2 - 二维线段树之四叉树写法

简介

由于这种写法比较亲民，我们先来看它。

众所周知，线段树的核心思想是分治。在维护一个区间是，我们先是把这个区间分割成两部分，分别维护，之后通过某种规律进行合并，将问题不断细分成一个个子问题，从而达到降低时间复杂度的的目的。（编者注：然而将这个思想实现为四分树不能降低时间复杂度。）

我们二维线段树同样可以采取类似的思想。既然一个区间我们将其分割成左右两个区间，运用类比的思想，我们可以把一个矩形分割成左上，右上，左下，右下四个小矩形分别维护。就像这张图：

模板代码

与普通线段树类似，它的结构体这样定义：

struct node{
    int l1, r1, l2, r2;
    int res; // 这里加上存储需要维护的信息的变量，如 sum 存矩阵和，maxn 存矩阵最大值，这里以 res 统括
    int lazy_tag; // 只有在矩阵修改的时候菜需要懒惰标记，其他时候可以不用
};
node tree[MAXN * MAXN << 4];

建树也和线段树一样：

int get_son(int p, int x){ return p * 4 - 2 + x; }
void build(int now, int x1, int y1, int x2, int y2){
    tree[now].x1 = x1; tree[now].y1 = y1; tree[now].x2 = x2; tree[now].y2 = y2;
    tree[now].tag_ass = -1; tree[now].tag_add = 0;
    if(x1 == x2 && y1 == y2){
        tree[now].sum = a[x1][y2];
        return ;
    }
    int midx = (x1 + x2) >> 1, midy = (y1 + y2) >> 1;
    if(x1 == x2){
        build(get_son(now, 0), x1, y1, x2, midy); build(get_son(now, 1), x1, midy + 1, x2, y2);
        push_up(now, 0);
    }else if(y1 == y2){
        build(get_son(now, 0), x1, y1, midx, y2); build(get_son(now, 1), midx + 1, y1, x2, y2);
        push_up(now, 0);
    }else{
        build(get_son(now, 0), x1, y1, midx, midy);
        build(get_son(now, 1), midx + 1, y1, x2, midy);
        build(get_son(now, 2), x1, midy + 1, midx, y2);
        build(get_son(now, 3), midx + 1, midy + 1, x2, y2);
        push_up(now, 1);
    }
}

修改和查询是一样的写法，就只写一种好了，以区间加法为例。

void update_add(int now, int x1, int y1, int x2, int y2, int val){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > tree[now].y2 || tree[now].y2 < tree[now].y1) return ;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        tree[now].tag_add += val;
        if(tree[now].tag_ass >= 0) tree[now].tag_ass += val;
        tree[now].sum += (tree[now].x2 - tree[now].x1 + 1) * (tree[now].y2 - tree[now].y1 + 1) * val;
        return ;
    }
    push_down(now);
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        update_add(get_son(now, 0), x1, y1, x2, y2, val);
        update_add(get_son(now, 1), x1, y1, x2, y2, val);
        push_up(now, 0);
    }else{
        for(int i = 0; i < 4; i++) update_add(get_son(now, i), x1, y1, x2, y2, val);
        push_up(now, 1);
    }
}

还有最重要的上传和下传：

void push_up(int now, int op){
    tree[now].sum = tree[get_son(now, 0)].sum + tree[get_son(now, 1)].sum;
    if(op == 0) return ;
    for(int i = 2; i < 4; i++) tree[now].sum += tree[get_son(now, i)].sum;
}
void push_down(int now){
    if(tree[now].tag_add != 0){
        if(tree[now].y1 == tree[now].y2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_add += tree[now].tag_add;
            tree[son1].tag_add += tree[now].tag_add;
            tree[son0].sum += (tree[son0].x2 - tree[son0].x1 + 1) * tree[now].tag_add;
            tree[son1].sum += (tree[son1].x2 - tree[son1].x1 + 1) * tree[now].tag_add;
        }else if(tree[now].x1 == tree[now].x2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_add += tree[now].tag_add;
            tree[son1].tag_add += tree[now].tag_add;
            tree[son0].sum += (tree[son0].y2 - tree[son0].y1 + 1) * tree[now].tag_add;
            tree[son1].sum += (tree[son1].y2 - tree[son1].y1 + 1) * tree[now].tag_add;
        }else{
            for(int i = 0; i < 4; i++){
                int son = get_son(now, i), s = (tree[son].x2 - tree[son].x1 + 1) * ((tree[son].y2 - tree[son].y1 + 1));
                tree[son].sum += s * tree[now].tag_add;
                tree[son].tag_add += tree[now].tag_add;
            }
        }
        tree[now].tag_add = 0;
    }
}

例题

例题一【模板】四叉树

~~好吧其实没有这个题目因为它是冷门数据结构的冷门写法啊~~

例题洛谷 P4514 上帝造题的七分钟

如题，有一个初始全为 0 的 n \times m 的矩阵，你需要进行下面两种操作：

L a b c d delta 将 (a,b),(c,d) 为顶点的矩形区域内的所有数字加上 delta。

k a b c d 求 (a,b),(c,d) 为顶点的矩形区域内所有数字的和。

~~但是用四叉树做这题应该铁定被卡的吧（捂脸~~

这道题的正解其实是二维树状数组，不过用二维线段树也是可以维护的（好像会被卡空间？）。（编者注：该题使用正确写法的线段树套线段树一般会被卡时间常数。） 这其实就是矩阵加法 + 矩阵求和。下面的代码拓展了一下，同时实现了矩阵推平赋值。

#include<bits/stdc++.h>
#define MAXN 1010
using namespace std;
typedef long long ll;
struct node{
    int x1, y1, x2, y2;
    ll tag_ass, tag_add, sum;
};
node tree[MAXN * MAXN << 2];
int n, m, q;
ll a[MAXN][MAXN];
/*
    四叉树时：
        x = 0 ——> 左上方子矩阵
        x = 1 ——> 右上方子矩阵
        x = 2 ——> 左下方子矩阵
        x = 3 ——> 右下方子矩阵
    二叉树时：
        x = 0 ——> 左/上方子矩阵
        x = 1 ——> 右/下方子矩阵
*/
int get_son(int p, int x){ return p * 4 - 2 + x; }
/*
    op = 0 ——> 二叉树
    op = 1 ——> 四叉树
*/
void push_up(int now, int op){
    tree[now].sum = tree[get_son(now, 0)].sum + tree[get_son(now, 1)].sum;
    if(op == 0) return ;
    for(int i = 2; i < 4; i++) tree[now].sum += tree[get_son(now, i)].sum;
}
void push_down(int now){
    if(tree[now].tag_add != 0){
        if(tree[now].y1 == tree[now].y2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_add += tree[now].tag_add;
            tree[son1].tag_add += tree[now].tag_add;
            tree[son0].sum += (tree[son0].x2 - tree[son0].x1 + 1) * tree[now].tag_add;
            tree[son1].sum += (tree[son1].x2 - tree[son1].x1 + 1) * tree[now].tag_add;
        }else if(tree[now].x1 == tree[now].x2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_add += tree[now].tag_add;
            tree[son1].tag_add += tree[now].tag_add;
            tree[son0].sum += (tree[son0].y2 - tree[son0].y1 + 1) * tree[now].tag_add;
            tree[son1].sum += (tree[son1].y2 - tree[son1].y1 + 1) * tree[now].tag_add;
        }else{
            for(int i = 0; i < 4; i++){
                int son = get_son(now, i), s = (tree[son].x2 - tree[son].x1 + 1) * ((tree[son].y2 - tree[son].y1 + 1));
                tree[son].sum += s * tree[now].tag_add;
                tree[son].tag_add += tree[now].tag_add;
            }
        }
        tree[now].tag_add = 0;
    }
    if(tree[now].tag_ass >= 0){
        if(tree[now].x1 == tree[now].x2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_ass = tree[now].tag_ass;
            tree[son1].tag_ass = tree[now].tag_ass;
            tree[son0].tag_add = tree[son1].tag_add = 0;
            tree[son0].sum = (tree[son0].y2 - tree[son0].y1 + 1) * tree[now].tag_ass;
            tree[son1].sum = (tree[son1].y2 - tree[son1].y1 + 1) * tree[now].tag_ass;
        }else if(tree[now].y1 == tree[now].y2){
            int son0 = get_son(now, 0), son1 = get_son(now, 1);
            tree[son0].tag_ass = tree[now].tag_ass;
            tree[son1].tag_ass = tree[now].tag_ass;
            tree[son0].tag_add = tree[son1].tag_add = 0;
            tree[son0].sum = (tree[son0].x2 - tree[son0].x1 + 1) * tree[now].tag_ass;
            tree[son1].sum = (tree[son1].x2 - tree[son1].x1 + 1) * tree[now].tag_ass;
        }else{
            for(int i = 0; i < 4; i++){
                int son = get_son(now, i), s = (tree[son].x2 - tree[son].x1 + 1) * ((tree[son].y2 - tree[son].y1 + 1));
                tree[son].tag_add = 0;
                tree[son].sum = s * tree[now].tag_ass;
                tree[son].tag_ass = tree[now].tag_ass;
            }
        }
        tree[now].tag_ass = -1;
    }
}
// 建树
void build(int now, int x1, int y1, int x2, int y2){
    tree[now].x1 = x1; tree[now].y1 = y1; tree[now].x2 = x2; tree[now].y2 = y2;
    tree[now].tag_ass = -1; tree[now].tag_add = 0;
    if(x1 == x2 && y1 == y2){
        tree[now].sum = a[x1][y2];
        return ;
    }
    int midx = (x1 + x2) >> 1, midy = (y1 + y2) >> 1;
    if(x1 == x2){
        build(get_son(now, 0), x1, y1, x2, midy); build(get_son(now, 1), x1, midy + 1, x2, y2);
        push_up(now, 0);
    }else if(y1 == y2){
        build(get_son(now, 0), x1, y1, midx, y2); build(get_son(now, 1), midx + 1, y1, x2, y2);
        push_up(now, 0);
    }else{
        build(get_son(now, 0), x1, y1, midx, midy);
        build(get_son(now, 1), midx + 1, y1, x2, midy);
        build(get_son(now, 2), x1, midy + 1, midx, y2);
        build(get_son(now, 3), midx + 1, midy + 1, x2, y2);
        push_up(now, 1);
    }
}
// 矩阵加法
void update_add(int now, int x1, int y1, int x2, int y2, int val){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > tree[now].y2 || tree[now].y2 < tree[now].y1) return ;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        tree[now].tag_add += val;
        if(tree[now].tag_ass >= 0) tree[now].tag_ass += val;
        tree[now].sum += (tree[now].x2 - tree[now].x1 + 1) * (tree[now].y2 - tree[now].y1 + 1) * val;
        return ;
    }
    push_down(now);
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        update_add(get_son(now, 0), x1, y1, x2, y2, val);
        update_add(get_son(now, 1), x1, y1, x2, y2, val);
        push_up(now, 0);
    }else{
        for(int i = 0; i < 4; i++) update_add(get_son(now, i), x1, y1, x2, y2, val);
        push_up(now, 1);
    }
}
// 矩阵赋值
void update_ass(int now, int x1, int y1, int x2, int y2, int val){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > tree[now].y2 || tree[now].y2 < tree[now].y1) return ;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        tree[now].tag_add = 0;
        tree[now].tag_ass = val;
        tree[now].sum = (tree[now].x2 - tree[now].x1 + 1) * (tree[now].y2 - tree[now].y1 + 1) * val;
        return ;
    }
    push_down(now);
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        update_ass(get_son(now, 0), x1, y1, x2, y2, val);
        update_ass(get_son(now, 1), x1, y1, x2, y2, val);
        push_up(now, 0);
    }else{
        for(int i = 0; i < 4; i++) update_ass(get_son(now, i), x1, y1, x2, y2, val);
        push_up(now, 1);
    }
}
// 查询矩阵中所有元素的和
ll query(int now, int x1, int y1, int x2, int y2){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > tree[now].y2 || tree[now].y2 < tree[now].y1) return 0;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        return tree[now].sum;
    }
    push_down(now);
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        return query(get_son(now, 0), x1, y1, x2, y2) + query(get_son(now, 1), x1, y1, x2, y2);
    }else{
        ll res = 0;
        for(int i = 0; i < 4; i++) res += query(get_son(now, i), x1, y1, x2, y2);
        return res;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%lld",&a[i][j]);
        }
    }
    build(1, 1, 1, n, m);
    scanf("%d",&q);
    for(int i = 1; i <= q; i++){
        int op, x1, y1, x2, y2;
        scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
        if(op == 1){
            ll val; scanf("%lld",&val);
            update_add(1, x1, y1, x2, y2, val);
        }else if(op == 2){
            ll val; scanf("%lld",&val);
            update_ass(1, x1, y1, x2, y2, val);
        }else printf("%lld\n",query(1, x1, y1, x2, y2));
    }
    return 0;
}

例题二 HDU 4819 Mosaic

给定一个 n\times n 的矩阵以及其初始元素。q 次操作，每次操作将 (x,y) 位置的元素改成中心为 (x, y)，边长为 l 的正方形中的元素的最大值加上最小值除以二，并输出修改后该元素的值。

这题能够用四叉树来做的一个很重要的原因是，它的查询几乎是一个正方形，至于为什么后面会提到。其他的属于基本操作。注意，所要求查询的正方形的顶点可能在矩形范围之外，这时需要判断一下，即对 n 取 \min。

代码如下。~~可惜我人傻常数大。~~

#include<bits/stdc++.h>
#define MAXN 805
#define INF 0x3f3f3f3f
using namespace std;
struct node{
    int x1, y1, x2, y2;
    int max_res, min_res;
};
node tree[MAXN * MAXN << 2];
int t, n, q;
int a[MAXN][MAXN];
int get_son(int p, int x){ return p * 4 - 2 + x; }
void push_up(int now, int op){
    tree[now].max_res = max(tree[get_son(now, 0)].max_res, tree[get_son(now, 1)].max_res);
    tree[now].min_res = min(tree[get_son(now, 0)].min_res, tree[get_son(now, 1)].min_res);
    if(op == 0) return ;
    for(int i = 2; i < 4; i++) tree[now].max_res = max(tree[now].max_res, tree[get_son(now, i)].max_res);
    for(int i = 2; i < 4; i++) tree[now].min_res = min(tree[now].min_res, tree[get_son(now, i)].min_res);
}
void build(int now, int x1, int y1, int x2, int y2){
    tree[now].x1 = x1; tree[now].y1 = y1; tree[now].x2 = x2; tree[now].y2 = y2;
    if(x1 == x2 && y1 == y2){
        tree[now].max_res = tree[now].min_res = a[x1][y2];
        return ;
    }
    int midx = (x1 + x2) >> 1, midy = (y1 + y2) >> 1;
    if(x1 == x2){
        build(get_son(now, 0), x1, y1, x2, midy); build(get_son(now, 1), x1, midy + 1, x2, y2);
        push_up(now, 0);
    }else if(y1 == y2){
        build(get_son(now, 0), x1, y1, midx, y2); build(get_son(now, 1), midx + 1, y1, x2, y2);
        push_up(now, 0);
    }else{
        build(get_son(now, 0), x1, y1, midx, midy);
        build(get_son(now, 1), midx + 1, y1, x2, midy);
        build(get_son(now, 2), x1, midy + 1, midx, y2);
        build(get_son(now, 3), midx + 1, midy + 1, x2, y2);
        push_up(now, 1);
    }
}
void update(int now, int x, int y, int val){
    if(tree[now].x1 == tree[now].x2 && tree[now].y1 == tree[now].y2){
        tree[now].max_res = tree[now].min_res = val;
        return ;
    }
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        int son0 = get_son(now, 0), son1 = get_son(now, 1);
        if(tree[son1].x1 > x || tree[son1].x2 < x || tree[son1].y1 > y || tree[son1].y2 < y) update(get_son(now, 0), x, y, val);
        else update(get_son(now, 1), x, y, val);
        push_up(now, 0);
    }else{
        for(int i = 0; i < 4; i++){
            int son = get_son(now, i);
            if(tree[son].x1 > x || tree[son].x2 < x || tree[son].y1 > y || tree[son].y2 < y) continue;
            update(son, x, y, val);
            break;
        }
        push_up(now, 1);
    }
}
int query_max(int now, int x1, int y1, int x2, int y2){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > y2 || tree[now].y2 < y1) return -INF;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        return tree[now].max_res;
    }
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        return max(query_max(get_son(now, 0), x1, y1, x2, y2), query_max(get_son(now, 1), x1, y1, x2, y2));
    }else{
        int res = -INF;
        for(int i = 0; i < 4; i++) res = max(res, query_max(get_son(now, i), x1, y1, x2, y2));
        return res;
    }
}
int query_min(int now, int x1, int y1, int x2, int y2){
    if(tree[now].x1 > x2 || tree[now].x2 < x1 || tree[now].y1 > y2 || tree[now].y2 < y1) return INF;
    if(tree[now].x1 >= x1 && tree[now].x2 <= x2 && tree[now].y1 >= y1 && tree[now].y2 <= y2){
        return tree[now].min_res;
    }
    if(tree[now].x1 == tree[now].x2 || tree[now].y1 == tree[now].y2){
        return min(query_min(get_son(now, 0), x1, y1, x2, y2), query_min(get_son(now, 1), x1, y1, x2, y2));
    }else{
        int res = INF;
        for(int i = 0; i < 4; i++) res = min(res, query_min(get_son(now, i), x1, y1, x2, y2));
        return res;
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++) scanf("%d",&a[i][j]);
        }
        build(1, 1, 1, n, n);
        scanf("%d",&q);
        while(q--){
            int x, y, l;
            scanf("%d%d%d",&x,&y,&l);
            int x1 = max(x - l / 2, 1), x2 = min(x + l / 2, n);
            int y1 = max(y - l / 2, 1), y2 = min(y + l / 2, n);
            int res_min = query_min(1, x1, y1, x2, y2), res_max = query_max(1, x1, y1, x2, y2);
            int res = (res_min + res_max) / 2;
            printf("%d\n",res);
            update(1, x, y, res);
        }
    }
    return 0;
}

缺陷

四叉树想法确实是好的，但是它能否和一维线段树一样时间复杂度优秀呢？很遗憾，答案是否定的。

虽然它的复杂度看上去是 O(n \log^2 n)，但是想法是美好的，现实是残酷的，想要吧这个做法卡掉很简单，只需要一次查询或修改一个长度为 n，但是宽度为 1 的矩形就好了。由于它的分割方法，它最终不会像普通线段树那样维护一整段，而是会变成 n 个 1\times 1 的小正方形，此时它的复杂度就飙升到 O(n^2\log n) 了。（编者注：实际上好像也没有这么高。考虑会在每个节点中递归访问正确方向的其中 2 个子节点。由于四分树中最后一层合计访问到 n 个节点，则倒数第 i 层会访问到 \frac{n}{2^{i-1}} 个节点，因此单次复杂度为 O(n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \cdots) = O(n)，总复杂度 O(n^2)。）

如果你不理解的话，我们来模拟一下这个过程，以一个 4 \times 4 的正方形矩阵为例，我们现在查询左上角为 (1, 1)，右下角为 (1,4) 的矩形，也就是第一行。

首先，我们落在根节点，蓝色是我们当前所在的矩形：

接着，我们会查询它的左上矩形和右上矩形，如下图中橙色和绿色的两个矩形：

继续分割，橙色正方形和绿色正方形各自查询它们的左上矩形和右上矩形，对应下图中最上面一行的四种颜色的矩形：

回到例题二，它之所以可以用四叉树做法做，是因为它的查询的矩形贴近正方形，这样的情况下复杂度是较为优秀的。（编者注：准确的说应该是效率勉强可以接受。关于正方形查询的四分树复杂度没有找到严格证明。）

在最劣情况下，四叉树相当于单点查询了，效率大大减小。为了解决这个不利的困境，我们要推出另一种做法：树套树。

Lesson 3 - 二维线段树之树套树写法

简介

树套树这种方法不仅仅在二维线段树中有用到，在很多其他场合也可以用到。其包括线段树套线段树，线段树套平衡树，平衡树套线段树，树状数组套权值线段树，分块套树状数组等多种类型。每种类型都有着其用途。而我们要讲的二维线段树，它所运用的是线段树套线段树。

顾名思义，线段树套线段树，就是线段树上每一个结点都是另一颗线段树。

我们首先构造一颗一维线段树，它维护的是横向的区间。还是以 4 \times 4 的正方形矩阵为例，这颗线段树上的 [2,3] 维护的是下图中橙色区域的信息：

由于是树套树，所以这个节点同样对应一棵线段树。这棵线段树维护的是纵向区间的信息。如这个结点做对应的线段树中的 [1,3] 维护的就是下图中绿色的区域：

也就是说，我们用外层的一棵线段树维护横向的区间，而对于每一个结点，在它上面建一棵内层的维护纵向的区间。横向区间 [l_1,r_1] 所对应的外层线段树中的结点所对应的内层线段树中的对应纵向区间 [l_2,r_2] 的结点所维护的信息，就是左上角 (l1, l2)，右下角 (r1, r2) 的矩形的信息。~~（好绕啊）~~

模板代码 1

考虑下面这个问题。

给定一个 n \times m 的矩阵，初始时元素均为 0，你需要维护一下操作：

1 x y k，将矩阵中 (x,y) 位置的元素加上 k。

2 x1 y1 x2 y2，查询左上角为 (x1, y1)，右下角为 (x2, y2) 的矩阵中的元素和。

这是一个单点修改，矩阵查询的模板。具体细节参见注释。

#include<bits/stdc++.h>
#define MAXN 1010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
typedef long long ll;
// 内层线段树节点，维护纵坐标
struct node_y{
    int l, r;
    ll res;
};
// 内层线段树
struct tree_y{
    node_y tree[MAXN << 2];
    void push_up(int now){ tree[now].res = tree[lson].res + tree[rson].res; };
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
        push_up(now);
    }
    /*
        实际上，内层线段树的修改与查询有两种写法，这是其中一种，也是我们通常情况下使用的。
        另一种称为“标记永久化”，在后面会有提到。
    */
    void update(int now, int y, int k){
        if(tree[now].l == tree[now].r){
            tree[now].res += k;
            return ;
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(y <= mid) update(lson, y, k);
        else update(rson, y, k);
        push_up(now);
    }
    ll query(int now, int l, int r){
        if(tree[now].l >= l && tree[now].r <= r) return tree[now].res;  
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) return query(lson, l, r);
        else if(l > mid) return query(rson, l, r);
        else return query(lson, l, mid) + query(rson, mid + 1, r);
    }
};
// 外层线段树节点，维护横坐标
struct node_x{
    int l, r;
    tree_y tr;
};
// 外层线段树
struct tree_x{
    int m;
    node_x tree[MAXN << 2];
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r; tree[now].tr.build(1, 1, m);
        if(tree[now].l == tree[now].r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    void update(int now, int x, int y, int k){
        /*
            这里沿途经过的点都要对其对应的内层线段树进行修改。
            因为显然要修改的点包在了这里面。
        */
        tree[now].tr.update(1, y, k);
        if(tree[now].l == tree[now].r) return ;
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(x <= mid) update(lson, x, y, k);
        else update(rson, x, y, k);
    }
    ll query(int now, int lx, int rx, int ly, int ry){
        if(tree[now].l >= lx && tree[now].r <= rx){
            // 找到外层结点对应的区间后，查询内层线段树的区间
            return tree[now].tr.query(1, ly, ry);
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(rx <= mid) return query(lson, lx, rx, ly, ry);
        else if(lx > mid) return query(rson, lx, rx, ly, ry);
        else return query(lson, lx, mid, ly, ry) + query(rson, mid + 1, rx, ly, ry);
    }
};
tree_x tree;
int n, m, q;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    tree.m = m; tree.build(1, 1, n);
    while(q--){
        int op;
        scanf("%d",&op);
        if(op == 1){
            int x, y, k;
            scanf("%d%d%d",&x,&y,&k);
            tree.update(1, x, y, k);
        }else{
            int x1, y1, x2, y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%lld\n",tree.query(1, x1, x2, y1, y2));
        }
    }
}

标记永久化

这种写法的时间复杂度足够优秀，而且不向四叉树那样会假掉。然而，同样有缺点。

考虑从这样一个问题：

给定一个 n \times m 的矩阵，初始时元素均为 0，你需要维护一下操作：

1 x1 y1 x2 y2 k，将左上角为 (x1, y1)，右下角为 (x2, y2) 的矩阵中的所有元素变成 k（保证 k \ge 当前修改的矩阵中的最大值）。

2 x1 y1 x2 y2，查询左上角为 (x1, y1)，右下角为 (x2, y2) 的矩阵中的最大值。

与之前的题目不同的是，这里的修改变成了矩阵修改（查询和修改略有变化，并加上了一些限制，这与后面提到的，树套树写法的局限性有关）。类比普通线段树，我们很自然的会想到懒惰标记。

你可以尝试在不看之后的文章的情况下写一下，你会发现，你的线段树跑得很慢。归根结底，问题其实出现在懒惰标记的下传上。

因为每一个结点对应一棵线段树，每次下传就会对当前节点的儿子节点的整棵线段树进行下传操作，单次下传的时间复杂度是 O(n\log n) 的，总时间复杂度非常的慢。为了解决这个问题，我们需要一种奇妙的方法，叫做标记永久化。下面简单介绍一下。

什么是标记永久化呢？就是修改时留下的懒惰标记并不下传，同时也不删除，而是留在打上标记的那一个节点，而经过这个节点时，就加上这个点懒惰标记造成的影响。

如图是一棵一维线段树，我们假定一开始所有元素的值都为 1，在执行了 “[1,3] 加上 3 ” 和 “[1,2] 加上 2” 两次操作时候的状态，节点上面的红字表示懒惰标记，没有红字的代表 0：

接下来我们查询 [1,1] 的值，我们先后经过了 [1,4]，[1,2]，[1,1] 三个节点，将经过的节点的懒惰标记加起来（期间无需下传），得到答案 5，这就是标记永久化的过程。

例题：洛谷 P3372 【模板】线段树 1

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 k。

求出某区间每一个数的和。

一维线段树的标记永久化代码如下：

#include<bits/stdc++.h>
#define MAXN 100010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
typedef long long ll;
struct node{
    int l, r;
    ll res, lazy_tag;
};
node tree[MAXN << 2];
int n, m;
int a[MAXN];
void push_up(int now){
    tree[now].res = tree[lson].res + tree[rson].res;
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r){
        tree[now].res = a[l];
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(now);
}
void update(int now, int l, int r, ll x){
    // 这里是修改对沿途结点造成的影响，相当与在后面上传。
    tree[now].res += x * (r - l + 1);
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].lazy_tag += x;
        return ;
    }
    // 注意到这里并没有 push_down()
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) update(lson, l, r, x);
    else if(l > mid) update(rson, l, r, x);
    else update(lson, l, mid, x), update(rson, mid + 1, r, x);
    // 注意到这里并没有 push_up()
}
// sum 记录的就是沿途标记的影响
ll query(int now, int l, int r, ll sum){
    if(tree[now].l >= l && tree[now].r <= r) return tree[now].res + sum * (r - l + 1);
    // 注意到这里并没有 push_down()
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return query(lson, l, r, sum + tree[now].lazy_tag);
    else if(l > mid) return query(rson, l, r, sum + tree[now].lazy_tag);
    else return query(lson, l, mid, sum + tree[now].lazy_tag) + query(rson, mid + 1, r, sum + tree[now].lazy_tag);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1, 1, n);
    for(int i = 1; i <= m; i++){
        int op, l, r; ll x;
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%lld",&l,&r,&x);
            update(1, l, r, x);
        }else{
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1, l, r, 0));
        }
    }
    return 0;
}

模板代码

由于无需下传，标记永久化就可以用于各种树套树上，（编者注：平衡树应该很难标记永久化吧……） 同样的，二维线段树也适用。

现在我们再来回顾上面的问题。

给定一个 n \times m 的矩阵，初始时元素均为 0，你需要维护一下操作：

1 x1 y1 x2 y2 k，将左上角为 (x1, y1)，右下角为 (x2, y2) 的矩阵中的所有元素变成 k（保证 k \ge 当前修改的矩阵中的最大值）。

2 x1 y1 x2 y2，查询左上角为 (x1, y1)，右下角为 (x2, y2) 的矩阵中的最大值。

首先是内层的线段树，内层的线段树的定义要写在外层线段树之前，因为后者会调用前者。内层线段树和普通的线段树是一样的，是否标记永久化都可以：

/*
    内层线段树结点的结构体，维护纵向区间
    其内部与普通线段树相同
*/
struct node_y{
    int l, r;
    ll res, lazy_tag;

};
/*
    内层线段树的结构体
    写在一个结构体里，可以使得代码更加简洁。
*/
struct tree_y{
    node_y tree[MAXN << 2];
    void push_up(int now){ tree[now].res = max(tree[lson].res, tree[rson].res); }
    // 内层线段树可以正常下传懒惰标记
    // 根据不同的要求会有不同的懒惰标记
    void push_down(int now){
        if(tree[now].lazy_tag != -1){
            tree[lson].res = tree[rson].res = tree[now].lazy_tag;
            tree[lson].lazy_tag = tree[rson].lazy_tag = tree[now].lazy_tag;
            tree[now].lazy_tag = -1;
        }
    }
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r; tree[now].lazy_tag = -1;
        if(l == r) return ; // 这里默认初始矩阵为 0，如果不是 0 而是 a，这里应该让 tree[now].res = a 之后在返回
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    // 内层线段树由于已经确定了横向的区间，修改时只需要传入纵向的区间就可以了
    void update(int now, int l, int r, int val){
        if(tree[now].l >= l && tree[now].r <= r){
            tree[now].res = tree[now].lazy_tag = val;
            return;
        }
        push_down(now);
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) update(lson, l, r, val);
        else if(l > mid) update(rson, l, r, val);
        else update(lson, l, mid, val), update(rson, mid + 1, r, val);
        push_up(now);
    }
    // 与修改类似
    ll query(int now, int l, int r){
        if(tree[now].l >= l && tree[now].r <= r) return tree[now].res;  
        push_down(now);
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) return query(lson, l, r);
        else if(l > mid) return query(rson, l, r);
        else return max(query(lson, l, mid), query(rson, mid + 1, r));
    }
};

接下来是稍微复杂一点的外层线段树，注释应该比较详细：

/*
    外层线段树结点的结构体，维护横向区间
    每个外层的节点会对应一个内层的线段树
*/
struct node_x{
    int l, r;
    /*
        这里依旧有懒惰标记的存在，只是我们不会下传，而是经过它是加上它的影响。
        懒惰标记不再是普通线段树的 int 或者 long long 之类的类型，它同样是一棵线段树，因为不是所有的纵向区间的懒惰标记都是一样的
    */
    tree_y lazy_tag;
    tree_y tr; // 对应的内层线段树
};
/*
    外层线段树的结构体
    同样作为一个结构体来处理
*/
struct tree_x{
    int m; // 表示纵向总长度，便于内层建树
    node_x tree[MAXN << 2];
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r;
        tree[now].tr.build(1, 1, m); tree[now].lazy_tag.build(1, 1, m); // 别忘了在这里对内层线段树建树，每个结点都要，而不是仅仅叶子结点
        if(tree[now].l == tree[now].r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    void update(int now, int l1, int r1, int l2, int r2, int val){
        /*
            相信很多人都不理解为什么这里也要对内层修改，这样不是相当于扩大了范围吗？
            仔细思考会发现，不修改是绝对不行的，因为当前所覆盖的范围肯定包括了我们要修改的矩形，也就是说，当前结点的答案是有可能由修改的那个矩形中更新过来的
            而如果我们仅仅在当前覆盖的范围等于我们要修改的矩形的范围是修改，那么在更大范围的查询时就会出问题
            比如当前的横向区间是 [1,4]，最大值为 1，而我们修改的矩形的左上角和右下角分别是 (2,2) 和 (3,3)，修改后的值为 5
            如果没有这里的修改，再查询左上角和右下角分别是 (1,1) 和 (4,4) 的矩形的时候，我们得到的答案将会是 1
            可是修改貌似也不对。在一般情况下确实是错误的，这样的要求也造就了树套树写法的局限性
            对于矩阵推平 + 矩阵最大值的题目，我们只有在保证矩阵推平所赋的值不小于推平前的矩阵最大值的时候才保证树套树写法的正确性，求最小值同理。
            至于为什么这种情况下是对的，显然，当前所覆盖的范围肯定包括了我们要修改的矩形
            既然这个矩形被赋的值会大于当前区域的最大值，那么当前覆盖的范围的最大值一定来自那个矩形
            可以自己举例理解一下
        */
        tree[now].tr.update(1, l2, r2, val);
        if(tree[now].l >= l1 && tree[now].r <= r1){
            // 懒惰标记的修改就只需要在这里修改了
            tree[now].lazy_tag.update(1, l2, r2, val);
            return ;
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r1 <= mid) update(lson, l1, r1, l2, r2, val);
        else if(l1 > mid) update(rson, l1, r1, l2, r2, val);
        else update(lson, l1, mid, l2, r2, val), update(rson, mid + 1, r1, l2, r2, val);
    }
    ll query(int now, int l1, int r1, int l2, int r2){
        if(tree[now].l >= l1 && tree[now].r <= r1) return tree[now].tr.query(1, l2, r2);
        int mid = (tree[now].l + tree[now].r) >> 1;
        // 懒惰标记在这里用上，记录是沿途经过的点的懒惰标记的影响
        ll res = tree[now].lazy_tag.query(1, l2, r2);
        if(r1 <= mid) return max(res, query(lson, l1, r1, l2, r2));
        else if(l1 > mid) return max(res, query(rson, l1, r1, l2, r2));
        else return max(res, max(query(lson, l1, mid, l2, r2), query(rson, mid + 1, r1, l2, r2)));
    }
};

缺陷

正如代码中提到的，树套树的写法是有限制的。我们只有在保证矩阵推平所赋的值不小于推平前的矩阵最大值的时候才保证树套树写法的正确性，求最小值同理。同时，它也不可以求矩阵和，原因还是在与外层线段树第 41 行的修改。这里会把修改的范围扩大。

所以，树套树在面对这些情况的时候就显得很无能为力。但是，抛开这个缺陷不谈，它其实比四叉树优秀太多了。事实上，在算法竞赛中少有的二维线段树题目中，大多数的题目都可以用树套树写法来做。

至于为什么能够做单点修改，那显然是因为它根本不需要懒惰标记，所以也就无所谓标记下传和标记永久化了。

例题

例题一 POJ 1195 Mobile phones

初始有一个二维矩阵，其中元素均为 0，要求维护下面 2 个操作：

某点 (x,y) 值增加 val

查询子矩阵的和

这就是单点修改，矩阵查询的模板题目了，可以翻看之前的模板代码。

例题二 HDU - 1823 Luck and Love

原题传送门

有一个初始为空的集合，m 次操作。每次操作是以下两种操作之一：

I h a l（I 是一个字符，h 是正整数，a 和 l 是浮点数），表示有一个身高为 h，活泼度为 a，缘分值为 l 的人加入该集合中。

Q h1 h2 a1 a2，询问身高在 [h1, h2] 之间，活泼度在 [a1, a2] 之间的人的最大缘分值。如果没有满足以上条件的人那么输出 -1。

观察到修改与询问的形式和例题一很类似。我们可以做一个转化，以身高作为横坐标，以活泼度作为纵坐标，这样就变成了一个单点修改，矩阵查询的问题了。

然而还有一个问题就是活泼度是浮点数，我们显然不能够以浮点数作为下标来构建线段树。不过观察到题目中的限制：

保证所有浮点数都只有一位小数。

我们可以直接将其乘以 10，这样就变成了一个 [0,1000] 之间的正整数了。

需要注意的有两点：

题目所给的 h1 与 h2 并不保证 h1 \le h2，当 h1 > h2 是需要交换，a1 和 a2 同理。
可以有两个人身高和活泼度都相同，这个时候应该取他们两个间的最大值。

代码如下：

#include<bits/stdc++.h>
#define MAXN 1010
#define MAXM 210
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
struct node_y{
    int l, r;
    int res;
};
// 内层线段树
struct tree_y{
    node_y tree[MAXN << 2];
    void push_up(int now){ tree[now].res = max(tree[lson].res, tree[rson].res); };
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r;
        tree[now].res = -1;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
        push_up(now);
    }
    void update(int now, int y, int k){
        if(tree[now].l == tree[now].r){
            tree[now].res = max(tree[now].res, k);
            return ;
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(y <= mid) update(lson, y, k);
        else update(rson, y, k);
        push_up(now);
    }
    int query(int now, int l, int r){
        if(tree[now].l >= l && tree[now].r <= r) return tree[now].res;  
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) return query(lson, l, r);
        else if(l > mid) return query(rson, l, r);
        else return max(query(lson, l, mid), query(rson, mid + 1, r));
    }
};
struct node_x{
    int l, r;
    tree_y tr;
};
struct tree_x{
    int m;
    node_x tree[MAXM << 2];
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r; tree[now].tr.build(1, 1, m);
        if(tree[now].l == tree[now].r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    void update(int now, int x, int y, int k){
        tree[now].tr.update(1, y, k);
        if(tree[now].l == tree[now].r) return ;
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(x <= mid) update(lson, x, y, k);
        else update(rson, x, y, k);
    }
    int query(int now, int lx, int rx, int ly, int ry){
        if(tree[now].l >= lx && tree[now].r <= rx){
            return tree[now].tr.query(1, ly, ry);
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(rx <= mid) return query(lson, lx, rx, ly, ry);
        else if(lx > mid) return query(rson, lx, rx, ly, ry);
        else return max(query(lson, lx, mid, ly, ry), query(rson, mid + 1, rx, ly, ry));
    }
};
int n;
tree_x tree;
int main(){
    while(~scanf("%d",&n)){
        if(n == 0) break;
        tree.m = 1005; tree.build(1, 1, 205);
        while(n--){
            char op[5];
            scanf("%s",op + 1);
            if(op[1] == 'I'){
                int h, b; double a, l;
                scanf("%d%lf%lf",&h,&a,&l);
                b = a * 10 + 1;
                tree.update(1, h, b, l * 10);
            }else if(op[1] == 'Q'){
                int h1, h2, b1, b2; double a1, a2;
                scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2);
                b1 = a1 * 10 + 1; b2 = a2 * 10 + 1;
                if(h1 > h2) swap(h1, h2);
                if(b1 > b2) swap(b1, b2);
                int ans = tree.query(1, h1, h2, b1, b2);
                if(ans == -1) printf("%d\n",ans);
                else printf("%.1lf\n",ans / 10.0);
            }
        }
    }
}

例题三 SPOJ TETRIS3D - Tetris 3D

“俄罗斯方块”的作者决定制作一个3D版本的“俄罗斯方块”。有若干个长方体积木，它们将以一定的顺序下落，最底端是一个矩形平台。积木停止下落当且仅当它碰到了矩形平台或另一个已经停止下落的积木。它将保持这个位置不变直至游戏结束。

然而作者想要改变这个游戏的玩法。已知积木的下降顺序以及积木的起始释放位置，求游戏结束后积木堆最高点的高度。假设积木竖直下落且不旋转。为了描述方便起见，我们引入一个笛卡尔坐标系，原点为平台的顶点，轴与平台边缘平行。

乍看之下它像是区间加法，其实并非如此。我们抽象一下题意，就变成了：

初始矩形为 0，每次将一个子矩形修改为这个子矩形的最大值 +h，求 q 次修改之后整个矩形的最大值

这就是一个区间赋值 + 区间最大值，而且还保证了矩阵推平所赋的值不小于推平前的矩阵最大值，如此一来，我们就可以使用树套树了：

#include<bits/stdc++.h>
#define MAXN 1010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
struct node_y{
    int l, r;
    int res, lazy_tag;

};
struct tree_y{
    node_y tree[MAXN << 2];
    void push_up(int now){ tree[now].res = max(tree[lson].res, tree[rson].res); }
    void push_down(int now){
        if(tree[now].lazy_tag != -1){
            tree[lson].res = tree[rson].res = tree[now].lazy_tag;
            tree[lson].lazy_tag = tree[rson].lazy_tag = tree[now].lazy_tag;
            tree[now].lazy_tag = -1;
        }
    }
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r; tree[now].lazy_tag = -1;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    void update(int now, int l, int r, int val){
        if(tree[now].l >= l && tree[now].r <= r){
            tree[now].res = tree[now].lazy_tag = val;
            return;
        }
        push_down(now);
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) update(lson, l, r, val);
        else if(l > mid) update(rson, l, r, val);
        else update(lson, l, mid, val), update(rson, mid + 1, r, val);
        push_up(now);
    }
    int query(int now, int l, int r){
        if(tree[now].l >= l && tree[now].r <= r) return tree[now].res;
        push_down(now);
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) return query(lson, l, r);
        else if(l > mid) return query(rson, l, r);
        else return max(query(lson, l, mid), query(rson, mid + 1, r));
    }
};
struct node_x{
    int l, r;
    tree_y lazy_tag;
    tree_y tr;
};
struct tree_x{
    int m;
    node_x tree[MAXN << 2];
    void build(int now, int l, int r){
        tree[now].l = l; tree[now].r = r;
        tree[now].tr.build(1, 1, m); tree[now].lazy_tag.build(1, 1, m);
        if(tree[now].l == tree[now].r) return ;
        int mid = (l + r) >> 1;
        build(lson, l, mid); build(rson, mid + 1, r);
    }
    void update(int now, int l1, int r1, int l2, int r2, int val){
        tree[now].tr.update(1, l2, r2, val);
        if(tree[now].l >= l1 && tree[now].r <= r1){
            tree[now].lazy_tag.update(1, l2, r2, val);
            return ;
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r1 <= mid) update(lson, l1, r1, l2, r2, val);
        else if(l1 > mid) update(rson, l1, r1, l2, r2, val);
        else update(lson, l1, mid, l2, r2, val), update(rson, mid + 1, r1, l2, r2, val);
    }
    int query(int now, int l1, int r1, int l2, int r2){
        if(tree[now].l >= l1 && tree[now].r <= r1) return tree[now].tr.query(1, l2, r2);
        int mid = (tree[now].l + tree[now].r) >> 1;
        int res = tree[now].lazy_tag.query(1, l2, r2);
        if(r1 <= mid) return max(res, query(lson, l1, r1, l2, r2));
        else if(l1 > mid) return max(res, query(rson, l1, r1, l2, r2));
        else return max(res, max(query(lson, l1, mid, l2, r2), query(rson, mid + 1, r1, l2, r2)));
    }
};
tree_x tree;
int n, m, q;
int main(){
    scanf("%d%d%d",&n,&m,&q); n++; m++;
    tree.m = m; tree.build(1, 1, n);
    while(q--){
        int d, s, w, x, y;
        scanf("%d%d%d%d%d",&d,&s,&w,&x,&y);
        x++; y++; d--; s--;
        int res = tree.query(1, x, x + d, y, y + s);
        tree.update(1, x, x + d, y, y + s, res + w);
    }
    printf("%lld\n",tree.query(1, 1, n, 1, m));
    return 0;
}

四叉树做法例题二也是可以用树套树写法做的，大家不妨试试。

Lesson 4 - 总结

二维线段树在 OI 中几乎没有考过，以后再考的可能性也估计不大。但是其中的一些诸如标记永久化和树套树的思想是很有用的。

回到开头说的本蒟蒻出的题目，各位大佬可以抱有一点点期待，期待这次 CSP 回来之后能够出一场公开赛，届时这个题目很可能会在其中。（编者注：不用期待了。那道题因为使用四分树已经被赛团废了。）

（本博客完结，大佬轻喷 QWQ）