区间问题

统计一个区间内的数据 如区间 (l,r) 内 的点个数

前缀和

当数组不发生改变时 即区间内的点数 不发生变动 只不过查询的时候是换了区间查询 那么简单的方法使用前缀和 不仅代码简单 而且可以使得每次查询都做到O(1) 使用树状数组 和 线段树 也可以但复杂度太高了 尤其是线段树 不到万不得已 不要使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 一维度非常简单 关键是要想到
s[i] = a[1] + a[2] + .... a[i]

# 查询区间 (l,r) 内点的数量 即
a[l] + a[l+1] + ... + a[r] = s[r] - s[l-1]

# 二维
s[i,j] = 第i行 第j列 左上角所有元素的和

"""
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
"""

# 记数组元素为c 二维前缀和 的初始化为
for i in range(1,n+1):
	for j in range(1,n+1):
		s[i][j] = s[i-1][j] + s[i][j-1] + c - s[i-1][j-1]

# 对于范围 (x1,y1) (x2,y2) 区间内元素的查询操作的值为
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1][y1]

差分

区间改变 进行区间查询
这里的区间改变 对应到题目中 大多数 修改一个点后 对于之后一段区间内的结果都会产生影响
比如leectcode 1045 https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/ 题目要求的是一个区间的时间内正在做作业的学生人数 每个学生 在对应a点开始 做作业 b点 完成作业 如果[a,b] 到这个区间内当前做作业的人数有 10个人 但是在b+1 这个点 有一个人完成作业 但是在 c这个点之前都没有任何人完成作业 那么对于整个区间[b+1,c] 来说其中正在做作业的人数都是9个人 即一点修改 影响了整个区间 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 一维差分
# 给区间[l, r]中的每个数加上c
s[l]+=c
s[r+1]-=c

# 一维差分的初始化
for i in range(1,n+1):
	s[i] = s[i] + c
	s[i] = s[i+1] - c

"""
差分的查询操作
差分问题的查询 需要在完成一系列修改操作后 将差分数组还原为原数组
所以其实差分真正优化的是 对于数组的修改实现了O(1)
对于最后返回的值则要根据题目的定义 返回
"""
for i in range(1,n+1)
	s[i]+= s[i-1]

简单应用：
leetcode1450 原题链接:
https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        s = [0 for i in range(0, 1001 + 1)]
        for t1,t2 in zip(startTime,endTime):
            s[t1]+=1
            s[t2+1]-=1

        for i in range(1, 1000 + 1):
            s[i] += s[i - 1]

        return s[queryTime]