自学USACO 笔记：2025/1/14

userId_undefined

复仇者_THUNDER

荣耀黄金

2025-01-14 17:32:19

发布于：广东

13阅读
0回复
0点赞
自学USACO 笔记：2025/1/14：
二维前缀和：
	1.暴力解法：
		时间复杂度：O(qnm)。
	2.一维升级：
		把二维分成n个一维，再在一维的基础上算。
		时间复杂度：累加O(nm)全部查询O(qn)。
	3.二维：
		p[i][j] 代表从[0][0]到i j的累加结果。
        p[i][j] - p[x - 1][j] - p[i][y - 1] + p[x - 1][y - 1]。
        时间复杂度：累加O(nm) 全部查询O(q)。


二维差分：
    暴力解法：
        时间复杂度：O(qnm)。
    二维差分：
        解法与前缀和类似，反过来了。
        时间复杂度：累加O(nm) 全部查询O(q)。
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论