差分前缀和题目集

简介: 差分前缀和题目集

1.一维前缀和


sum[i]=sum[i-1] + a[i];


1.P5638 【CSGRound2】光骓者的荣耀

2.P2671 NOIP2015 普及组 求和(前缀和数组应用)

求和题解


2.二维前缀和(处理矩形的面积的权值)


sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];(只用一个数组,防止爆空间)


1.P1719 最大加权矩形(二维前缀和遍历所有矩形)

2.P2004 领地选择(二维前缀和遍历固定大小矩形)

3.P2280 [HNOI2003]激光炸弹

(二维前缀和遍历固定大小矩形,把每一个坐标看作矩形的一个块)


3.一维差分


i 到 j  加 k
cf[i]+=k;
cf[j+1]-=k;
sum[i]=sum[i-1]+cf[i];


1.P3397 地毯(差分数组)

2.P3406 海底高铁(实际问题应用)

3.P2879 [USACO07JAN] Tallest Cow S(实际问题应用)

4.P4552 [Poetize6] IncDec Sequence


目录
相关文章
|
12月前
前缀和、差分、二分
前缀和、差分、二分
65 0
|
3月前
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
|
4月前
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
48 4
【算法】前缀和与差分
|
3月前
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
|
6月前
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
6月前
|
存储 人工智能 BI
差分与前缀和
差分与前缀和
34 0
|
6月前
|
算法 测试技术 C++
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数
|
6月前
【每日一题Day122】LC1237找出给定方程的正整数解 | 双指针 二分查找
【每日一题Day122】LC1237找出给定方程的正整数解 | 双指针 二分查找
39 0
|
算法
基础算法(大数操作 前缀和 差分)
基础算法(大数操作 前缀和 差分)
69 0
|
人工智能 移动开发 机器人
蓝桥杯AcWing 题目题解 - 二分与前缀和、差分
蓝桥杯AcWing 题目题解 - 二分与前缀和、差分
148 0