首页 > 编程语言 >算法—差分

算法—差分

时间:2024-01-17 23:45:06浏览次数:27  
标签:x1 复杂度 差分 y1 算法 x2 y2

1.一维差分(实质:前缀和的逆运算)

给区间[l, r]中的每个数加上cB[l] += c, B[r + 1] -= c
image

上述操作可以免去构造一个新数组,可以直接给差分赋值

2.二维差分

给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上C
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

优点:将o(n)复杂度优化成o(1)的复杂度;

标签:x1,复杂度,差分,y1,算法,x2,y2
From: https://www.cnblogs.com/Eric0521/p/17971492

相关文章

  • 2024/1/17 算法笔记
    1.欧拉质数筛功能是给一个整数n查找小于等于n的所有质数。最后使用的是prime【i】//功能:查找n内第x个质数。boolisprime[100000010];//isprime[i]=1表示:i是素数intprime[6000010],cnt=0;//prime存质数voidgetprime(intn){//筛到n也就是n以内的质数memset(is......
  • 算法笔记之图论
    打开转盘锁你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字:'0','1','2','3','4','5','6','7','8','9'。每个拨轮可以自由旋转:例如把'9'变为'0','0'变为......
  • 算法笔记
    1.回溯法(Backtracking)应用:组合、排列、子集等组合型问题,0/1背包问题、图的着色问题等。时空复杂度:时空复杂度较高,指数级别。时间复杂度:O(2^n)或更高,其中n是问题规模。空间复杂度:O(n)或更高,取决于递归深度。特性:通过深度优先搜索遍历解空间。需要撤销选择,回溯到上一步......
  • 学习笔记——ST算法
    ST算法ST算法是一种运用倍增来解决RMQ问题也就是区间最值问题的算法。给定一个长度为\(N\)的序列\(A\),ST算法能在\(\mathcalO(NlogN)\)的时间预处理后,以\(\mathcalO(1)\)的时间在线回答区间最值问题。设\(F_{i,j}\)表示序列\(A\)中下标在子区间\(\left[i,......
  • 算法—前缀和
    1.一维前缀和S[i]=a[1]+a[2]+...a[i]//求s[n]a[l]+...+a[r]=S[r]-S[l-1]//求l-r的序列和2.二维前缀和S[i,j]=s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];第i行j列格子左上部分所有元素的和以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵的和为:S[......
  • 代码随想录算法训练营第一天| LeetCode704 二分查找,LeetCode35,LeetCode34,leetcode27.
    LeetCode704题目链接:704.二分查找-力扣(LeetCode)第一时间的想法:简单来说,二分法给我的印象就是想一条绳子上打很多的结,每次对折正好是一个结点,我们需要找到想要的结点比如(a)代码思路就是不断对折一直到绳子两端重合中间没有结点,最后剩下的就是要找的结点a了。......
  • 算法设计与分析-算法模板(不定期更新)
    算法大纲基础算法:模拟,分治,递归,排序,概率,堆进阶算法:DP,贪心,图论,计算几何,FFT,字符串22级期末考试题型:诚信承诺题、选择题5道、归并思想(175/184)、排序的变形题(155/169)、贪心(170/185)、线性动态规划(77/136)、区间动态规划(33/61)、最短路变形(3/25)、多源多汇最大流(12/23),之后......
  • 基础算法(三)二分查找---以“数的三次方”为例
    数的三次方根给定一个浮点数 n,求它的三次方根。输入格式共一行,包含一个浮点数 n。输出格式共一行,包含一个浮点数,表示问题的解。注意,结果保留 6 位小数。数据范围−10000≤n≤10000输入样例:1000.00输出样例:10.000000题解如下#include<iostream>usingnamespace......
  • 推荐算法之-召回中的随机负采样
    //二分查找deffetchBinarySearch(trainItems:Array[(String,Double)],target:Double):String={//valtrainItems=Array(("1",0),("2",1),("3",3),("4",4),("5",6))//valtarget=6.00000000......
  • 区域人数统计AI智能分析网关V4客流统计AI算法介绍及应用场景
    客流量统计AI算法是一种基于人工智能技术的数据分析方法,通过机器学习、深度学习等算法,实现对客流量的实时监测和统计。该算法主要基于机器学习和计算机视觉技术,其基本流程包括图像采集、图像预处理、目标检测、目标跟踪和客流量统计等步骤,通过在监控视频中识别和跟踪人的轮廓或特......