矩形加点求和

GitHub跳转原题关系图返回列表

矩形加、点查询：把矩形拆成 4 个带符号的二维差分点，用二维树状数组（外层 x、内层 y）求二维前缀和，单次 O(log²)。

OJ: roj

题目 ID: 1415

难度:提高+/省选-

标签:数据结构树状数组二维树状数组差分离散化python

创建: 2026-10-17 22:38

更新: 2026-10-17 23:20

前置题目

roj 1416矩形覆盖计数1416 教的是「矩形覆盖点」的扫描线做法：把矩形沿 x 拆成进入/离开事件，y 方向用差分 + 一维树状数组做区间加、单点查。本题只是把加矩形变成了在线操作，x 无法提前扫完，于是把这套「差分 + 前缀和」整体从一维升到二维，主解正是 1416 的二维版本。

形式化题目

维护一个带权矩形的集合，支持两种操作：

加矩形：把 $[l,r)\times[d,u)$ 内每个点的覆盖权值都加上 $w$ ；
查点：求点 $(x,y)$ 处当前的权值总和。

初始给出 $N$ 个矩形，再依次执行 $Q$ 次操作（加矩形或查点），加矩形与查点交错出现。

$N,Q \leqslant 10^5$ ，坐标 $\leqslant 10^9$ ， $w \geqslant 0$ 。

从前置题 1416 出发

roj-1416 矩形覆盖计数（矩形覆盖计数）解决的是静态版本：矩形全部给定，只有询问。它的做法是

沿 $x$ 扫描： $x=l$ 处让 y 区间 $[d,u)$ 加 1， $x=r$ 处减 1；y 方向用「差分 + 一维树状数组」实现区间加、单点查。

这里的关键是扫描线一次性把 x 维度消掉——因为所有矩形都知道，可以按 x 排好序一遍扫过去，之后每个询问只是一个一维查询。

本题的障碍恰好在于：加矩形和查点交错出现，第 $i$ 次询问必须看到它之前的所有加矩形、而看不到之后的。x 无法提前扫完，扫描线这条路走不通了。

那么换个角度：1416 的「一维差分 + 前缀和」其实和 x 无关，它只是把「区间加、单点查」转成了「单点加、前缀和」。这个转换在二维上同样成立，只是要同时处理 x 和 y 两个方向。

正解：二维差分 + 二维树状数组

关键观察

二维差分数组 $D$ 的定义是：原矩阵某点 $(x,y)$ 的值等于 $D$ 在 $[0,x]\times[0,y]$ 上的二维前缀和。

在这个定义下，"矩形加"就变成了 4 个单点加：

[l,r)\times[d,u) \text{ 全部加 } w \iff \begin{cases} D(l,d) \mathrel{+}= w \\ D(l,u) \mathrel{-}= w \\ D(r,d) \mathrel{-}= w \\ D(r,u) \mathrel{+}= w \end{cases}

这就是一维"区间加 = 差分两点"的二维版本：矩形的四条边各贡献一次正负抵消。要验证也很直接——把这四个点按二维前缀和展开， $[l,r)\times[d,u)$ 内每点恰好 $+w$ ，外面恰好 $+0$ 。

于是：

加矩形 $\to$ 4 次二维单点加；
查点 $\to$ 1 次二维前缀和。

两者都能交给二维树状数组，单次 $O(\log^2)$ 。

二维树状数组怎么建

二维树状数组是"树状数组套树状数组"：外层按 $x$ 建一棵 BIT，它的每个节点再挂一棵按 $y$ 的 BIT。

单点加 $(x,y,+v)$ ：外层沿 $x$ 的 lowbit 链走 $O(\log)$ 个节点，每个节点在内层 BIT 上对 $y$ 做一次单点加。
二维前缀和 $(x,y)$ ：外层沿 $x$ 的链走，每个节点取内层 $y$ 的前缀和。

坐标到 $10^9$ ，直接开 $10^9\times10^9$ 不可能。但所有会出现的坐标都能提前知道：加矩形只会触碰 $(l,d),(l,u),(r,d),(r,u)$ ，查点只会触碰 $(x,y)$ 。所以离线下把所有出现的 $(x,y)$ 收集起来，给每个外层节点单独收集它需要的 $y$ 集合并去重，内层 BIT 的长度就等于这个集合的大小。

这一步正是 1416 里 y 离散化的二维推广：1416 只有一张 y 表，这里每个外层节点各有一张。

思路

读入初始 $N$ 个矩形和 $Q$ 次操作，统一存成操作序列。
扫一遍操作序列，收集所有会落进 BIT 的坐标点：矩形取 4 个差分角，询问取点本身。
离散化 $x$ ，得到外层 BIT 长度；对每个外层节点，把落在它路径上的 $y$ 排序去重，作为内层 BIT 的坐标系。
按时间顺序重放操作：加矩形写 4 个带符号的单点加；查点输出二维前缀和。

为什么可以先离散化再重放：离散化只依赖"哪些坐标会出现"，而这个信息在输入里就有，与操作顺序无关；重放时严格按输入顺序，所以时间语义没有丢。

代码

C++ 版：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-17 23:02
 * update_at: 2026-10-17 23:02
 */
// main.cpp：矩形加、点查询——二维差分 + 二维树状数组。
//
// 1416（静态覆盖计数）的做法是：把「矩形覆盖」沿 x 拆成进/出事件，
// y 方向用差分 + 一维树状数组，靠一次扫描线把 x 维度消掉。
// 本题多了一个维度——时间：加矩形与查询交替出现，x 不能提前扫完。
// 于是把 1416 的「一维差分 + 前缀和」整体升到二维：
//
//   D 为二维差分数组。矩形 [l,r) x [d,u) 加 w 等价于 4 个单点加：
//     D(l,d) += w,  D(l,u) -= w,  D(r,d) -= w,  D(r,u) += w
//   点 (x,y) 的答案 = sum_{x'<=x, y'<=y} D(x',y')（二维前缀和）
//
// 二维前缀和/单点加用「树状数组套树状数组」：外层按 x 建 BIT，
// 每个外层节点再按 y 建一个 BIT。x、y 都先离线收集所有出现过的坐标做离散化，
// 这样不用真的开 1e9 * 1e9 的数组。单次操作 O(log^2)。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXOP = 200005; // 操作上限：初始 N 个矩形 + Q 次操作，N、Q <= 1e5

// 一条操作：type = 0 加矩形，type = 1 查询点
struct Op {
    int type;
    int l, d, r, u; // type 0：矩形 [l,r) x [d,u)
    ll w;           // type 0：矩形权值
    int x, y;       // type 1：询问点 (x,y)
};

Op op[MAXOP]; // 全部操作，按输入顺序
int q_cnt;    // 操作个数

int xs[MAXOP * 4]; // 离散化用的 x 坐标：矩形的 l、r 与询问的 x
int nx;            // 去重后的 x 个数

vector<int> col[MAXOP * 4];   // col[i]：外层节点 i 的内层 y 坐标，升序去重
vector<ll> bit[MAXOP * 4];    // bit[i]：外层节点 i 对应的一维树状数组

// 离散化表：值 -> 1 起的名次
int rank_of(int value, int table[], int n) {
    return lower_bound(table + 1, table + n + 1, value) - table;
}

// 把 (x, y) 这个点登记到外层 x 路径上，供后面建内层 y 表用
void prepare_point(int x, int y) {
    for (int i = rank_of(x, xs, nx); i <= nx; i += i & -i) col[i].push_back(y);
}

// 内层单点加：外层节点 i 里，把 y 名次 j 处加上 v
void inner_add(int i, int j, ll v) {
    int m = col[i].size();
    for (; j <= m; j += j & -j) bit[i][j] += v;
}

// 内层前缀和：外层节点 i 里，y 名次 <= j 的和
ll inner_sum(int i, int j) {
    ll s = 0;
    for (; j > 0; j -= j & -j) s += bit[i][j];
    return s;
}

// 二维单点加：D(x, y) += v。x 走外层 BIT，y 走每个外层节点的内层 BIT
void add_point(int x, int y, ll v) {
    for (int i = rank_of(x, xs, nx); i <= nx; i += i & -i) {
        // 同一个外层节点里，内层用 upper_bound 找到 y 的名次
        int j = lower_bound(col[i].begin(), col[i].end(), y) - col[i].begin() + 1;
        inner_add(i, j, v);
    }
}

// 二维前缀和：sum_{x'<=x, y'<=y} D(x', y')
ll prefix_sum(int x, int y) {
    ll s = 0;
    for (int i = rank_of(x, xs, nx); i > 0; i -= i & -i) {
        // 内层要取 <= y 的所有列，用 upper_bound 得到名次上界
        int j = upper_bound(col[i].begin(), col[i].end(), y) - col[i].begin();
        s += inner_sum(i, j);
    }
    return s;
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

    int xs_cnt = 0; // 收集到的 x 坐标个数，后面排序去重得到外层 BIT 长度
    // 初始矩形直接当成一开始就发生的「加矩形」操作
    for (int i = 1; i <= n; i++) {
        op[++q_cnt].type = 0;
        scanf("%d %d %d %d %lld", &op[q_cnt].l, &op[q_cnt].d, &op[q_cnt].r, &op[q_cnt].u, &op[q_cnt].w);
        xs[++xs_cnt] = op[q_cnt].l;
        xs[++xs_cnt] = op[q_cnt].r;
    }
    for (int i = 1; i <= q; i++) {
        int t;
        scanf("%d", &t);
        op[++q_cnt].type = t;
        if (t == 0) {
            scanf("%d %d %d %d %lld", &op[q_cnt].l, &op[q_cnt].d, &op[q_cnt].r, &op[q_cnt].u, &op[q_cnt].w);
            xs[++xs_cnt] = op[q_cnt].l;
            xs[++xs_cnt] = op[q_cnt].r;
        } else {
            scanf("%d %d", &op[q_cnt].x, &op[q_cnt].y);
            xs[++xs_cnt] = op[q_cnt].x;
        }
    }

    // x 离散化：外层 BIT 的下标
    sort(xs + 1, xs + xs_cnt + 1);
    nx = unique(xs + 1, xs + xs_cnt + 1) - (xs + 1);
    // y 不单独做全局离散化：每个外层节点的内层 y 表 col[i] 各管自己那一段

    // 预处理：把所有会出现的点（矩形的 4 个差分角 + 询问点）登记到外层路径上，
    // 这样每个外层节点需要的内层 y 集合就确定了
    for (int i = 1; i <= q_cnt; i++) {
        if (op[i].type == 0) {
            prepare_point(op[i].l, op[i].d);
            prepare_point(op[i].l, op[i].u);
            prepare_point(op[i].r, op[i].d);
            prepare_point(op[i].r, op[i].u);
        } else {
            prepare_point(op[i].x, op[i].y);
        }
    }
    for (int i = 1; i <= nx; i++) {
        sort(col[i].begin(), col[i].end());
        col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
        bit[i].assign(col[i].size() + 1, 0); // 下标 0 占位
    }

    // 按时间顺序处理：加矩形写 4 个差分点，查询取二维前缀和
    for (int i = 1; i <= q_cnt; i++) {
        if (op[i].type == 0) {
            int l = op[i].l, r = op[i].r, d = op[i].d, u = op[i].u;
            ll w = op[i].w;
            add_point(l, d, w);
            add_point(l, u, -w);
            add_point(r, d, -w);
            add_point(r, u, w);
        } else {
            printf("%lld\n", prefix_sum(op[i].x, op[i].y));
        }
    }
    return 0;
}

Python 版（同一算法）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-17 23:10
# update_at: 2026-10-17 23:10
#
# 矩形加点求和：二维差分 + 二维树状数组（rbook_nunjucks 代码模板风格）。
# 和前置题 1416（静态覆盖计数）的关系：1416 沿 x 做扫描线把一维消掉，
# y 用差分 + 一维树状数组；本题加矩形和查询交替，x 无法提前扫完，
# 于是把「差分 + 前缀和」整体升到二维：
#   矩形 [l,r) x [d,u) 加 w  <=>  D(l,d)+=w, D(l,u)-=w, D(r,d)-=w, D(r,u)+=w
#   点 (x,y) 的答案        <=>  sum_{x'<=x, y'<=y} D(x',y')
# 单点加/前缀和都用外层 x、内层 y 的树状数组，单次 O(log^2)。
# 一旦某个矩形已被加入，它就一直有效，所以离线把所有端点收集起来离散化即可。

import sys
from bisect import bisect_left, bisect_right

type Seq = list[int]  # 1 下标 int 序列，下标 0 占位不用


class Fenwick2D:
    """二维树状数组：x、y 都离散化，外层 x 每个节点各带一个内层 y 的树状数组。"""

    def __init__(self, xs: Seq, points: list[tuple[int, int]]) -> None:
        # xs 是 1 下标升序去重表；points 是全部会出现的 (x, y)
        self.nx = len(xs) - 1
        self.xs = xs
        # col[i]：外层节点 i 需要的内层 y 坐标（升序去重），bit[i] 与之等长 +1
        col: list[list[int]] = [[] for _ in range(self.nx + 1)]
        for x, y in points:
            i = self.x_rank(x)
            while i <= self.nx:
                col[i].append(y)
                i += i & -i
        for i in range(1, self.nx + 1):
            col[i] = sorted(set(col[i]))
        self.col = col
        self.tree: list[Seq] = [[0] * (len(col[i]) + 1) for i in range(self.nx + 1)]

    def x_rank(self, x: int) -> int:
        """x 的 1 起名次；调用方保证 x 在离散化表里。"""
        return bisect_left(self.xs, x, 1)  # xs 是 1 下标，bisect 结果天然是名次

    def add(self, x: int, y: int, value: int) -> None:
        """二维单点加：原矩阵的 (x, y) 处 += value。"""
        i = self.x_rank(x)
        while i <= self.nx:
            tree = self.tree[i]
            j = bisect_left(self.col[i], y) + 1  # 内层 1 起名次
            m = len(self.col[i])
            while j <= m:
                tree[j] += value
                j += j & -j
            i += i & -i

    def prefix_sum(self, x: int, y: int) -> int:
        """二维前缀和：x' <= x 且 y' <= y 的所有点之和。"""
        total = 0
        i = self.x_rank(x)
        while i > 0:
            tree = self.tree[i]
            j = bisect_right(self.col[i], y)  # <= y 的内层坐标个数
            while j > 0:
                total += tree[j]
                j -= j & -j
            i -= i & -i
        return total


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    pos = 0
    n = data[pos]
    q = data[pos + 1]
    pos += 2

    # 统一成操作序列：op = (type, l, d, r, u, w) 或 (1, x, y, 0, 0, 0)
    ops: list[tuple[int, int, int, int, int, int]] = []
    for _ in range(n):
        l, d, r, u, w = data[pos:pos + 5]
        pos += 5
        ops.append((0, l, d, r, u, w))
    for _ in range(q):
        t = data[pos]
        pos += 1
        if t == 0:
            l, d, r, u, w = data[pos:pos + 5]
            pos += 5
            ops.append((0, l, d, r, u, w))
        else:
            x, y = data[pos:pos + 2]
            pos += 2
            ops.append((1, x, y, 0, 0, 0))

    # 收集所有会落进树状数组的坐标：矩形的 4 个差分角 + 询问点
    xs: Seq = [0]
    points: list[tuple[int, int]] = []
    for t, l, d, r, u, w in ops:
        if t == 0:
            for x, y in ((l, d), (l, u), (r, d), (r, u)):
                xs.append(x)
                points.append((x, y))
        else:
            xs.append(l)
            points.append((l, d))

    xs = [0] + sorted(set(xs[1:]))  # 1 下标升序去重
    bit = Fenwick2D(xs, points)

    out: list[str] = []
    for t, l, d, r, u, w in ops:
        if t == 0:
            # 二维差分：矩形加 = 4 个带符号的单点加
            bit.add(l, d, w)
            bit.add(l, u, -w)
            bit.add(r, d, -w)
            bit.add(r, u, w)
        else:
            out.append(str(bit.prefix_sum(l, d)))  # 查询点存的是 (x, y) = (l, d)

    sys.stdout.write("\n".join(out) + ("\n" if out else ""))


if __name__ == "__main__":
    solve()

复杂度

时间： $O((N+Q)\log^2(N+Q))$ ，每次加矩形 4 次单点加、每次询问 1 次前缀和。
空间： $O((N+Q)\log(N+Q))$ ，每个坐标点被挂到 $O(\log)$ 个外层节点上。

实测（roj-local-judge-lite，cgroup 隔离）：C++ 19 个数据点全部 AC，最慢 2580 ms / 145 MiB（时限 10000 ms）；Python 同样全部 AC，但有 8 个点超过 10 s，属本仓库「Python 允许 TLE」的范围——算法与 C++ 同阶，只是常数大。

总结

从 1416 到 1415 的变化只有一句话：扫描线要求"x 能提前扫完"，加了在线操作后这条前提失效，于是把一维的「差分 + 前缀和」升到二维。
二维差分的核心公式要背下来：矩形加 = 4 个单点加， $(l,d)$ 和 $(r,u)$ 同号， $(l,u)$ 和 $(r,d)$ 反号。
二维树状数组靠"外层 BIT 的每个节点各带一张内层 y 表"来省内存；因为坐标能提前全部知道，所以可以离散化，不必开坐标值域那么大的数组。
这类"矩形加、点查询"的题目还有另一种做法——CDQ 分治按时间离线，也能做到 $O((N+Q)\log^2)$ ；二维树状数组的好处是不用想分治，代价是内存翻 $O(\log)$ 倍。

【题目描述】

二维平面上有 $N$ 个带权矩形。第 $i$ 个矩形的位置为

[l_i,r_i) \times [d_i,u_i) = \{(x,y)\in \mathbb{R}^2 \mid l_i\leq x < r_i,\ d_i \leq y < u_i\}

权值为 $w_i$ 。现在依次处理 $Q$ 个操作，操作分两种：

0 l d r u w：在 $[l,r) \times [d,u)$ 处添加一个权值为 $w$ 的新矩形；
1 x y：求所有包含点 $(x,y)$ 的矩形的权值之和。

【输入】

第一行包含两个整数 $N$ 和 $Q$ ，表示初始矩形个数和操作个数。

接下来 $N$ 行，第 $i$ 行包含五个整数 $l_i\ d_i\ r_i\ u_i\ w_i$ ，表示第 $i$ 个矩形的位置与权值。

接下来 $Q$ 行，每行描述一个操作：

0 l d r u w：添加一个权值为 $w$ 、位置为 $[l,r) \times [d,u)$ 的矩形；
1 x y：查询包含点 $(x,y)$ 的矩形权值之和。

【输出】

对每个 1 x y 的查询操作，输出一行一个整数，表示所有包含点 $(x,y)$ 的矩形的权值之和。

【输入样例】

text

1
2
3
4
5
6
7
8
9
10
11
12
13
144 9
1 2 2 3 1
1 1 2 5 10
2 2 5 5 100
3 1 5 2 1000
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3

【输出样例】

text

【输入样例2】

text

1
2
3
4
5
6
7
8
9
10
112 8
1 2 2 3 1
1 1 2 5 10
1 1 2
1 2 3
0 1 1 3 3 100
1 1 2
1 2 3
0 2 1 3 5 1000
1 1 2
1 2 3

【输出样例2】

text

【数据范围】

$1 \leq N \leq 100000$
$1 \leq Q \leq 100000$
$0 \leq l_i < r_i \leq 10^9$
$0 \leq d_i < u_i \leq 10^9$
$0 \leq w_i \leq 10^9$
对于 0 l d r u w 操作： $0 \leq l < r \leq 10^9$ ， $0 \leq d < u \leq 10^9$ ， $0 \leq w \leq 10^9$
对于 1 x y 操作： $0 \leq x, y \leq 10^9$

【来源】

Library Checker（yosupo06） rectangle_add_point_get