首页 > 其他分享 >差分数组

差分数组

时间:2022-09-26 08:22:13浏览次数:56  
标签:前缀 个数 差分 修改 数组 区间

数据量不大时频繁的区间修改问题

设d为差分数组

对区间[l, r] 加x,则d[l] += x, d[r + 1] -= x

那么原数组中,第i个数的值为d从0到i的前缀和

证明:

为什么时0到i的前缀和呢?

因为对d的操作是对称的,如果i不在某个修改区间,则求前缀和时因为对称性会消除那个区间修改

否则 会加上左端点的修改,而右端点不会加上

 

区间查询个数时,求sum(连续单点符合的个数 - 1)即可

 

标签:前缀,个数,差分,修改,数组,区间
From: https://www.cnblogs.com/WTSRUVF/p/16729639.html

相关文章

  • JavaScript 数组常用方法大全
    Array对象所有方法concat()方法合并多个数组,返回一个新数组join() 方法将数组合并为字符串,用指定的字符分割pop()方法删除成员(从后) 并返回该被删......
  • C语言中的变长数组
    问:C语言中定义数组大小的时候可以使用变量吗?还是只能使用常量或者常量表达式??1 目前经常使用的C语言有三个版本,分别是C89、C99和C11。C89(也称ANSIC)是较早的版本,也是......
  • go 稀疏数组
     稀疏数组实现:packagemainimport"fmt"typeSparseArraystruct{ colint rowint valueint}funcmain(){ //源数据格式: /* 000......
  • 怎么写出数组扁平化?如何手写flat函数
    手写一下数组扁平化flat(),但是发现居然没有一个能够完成写出来,所以打算总结一下如果遇到了数组扁平化的题目(也可以叫做手动封装flat()方法),到底应该怎么写,怎么写可......
  • js数组去重的方法
    一、利用Set()+Array.from()Set对象:是值的集合,你可以按照插入的顺序迭代它的元素。Set中的元素只会出现一次,即Set中的元素是唯一的。Array.from() 方法:对一个类似数组......
  • 数组遍历的方法
    数组遍历的方法forEach类似与for循环不会改变原数组将数组中的2全部加1constarr=[1,2,3,2]varnewArr=[]arr.forEach(v=>{if(v===2){v=v+1}......
  • vue中检测不到数组或者对象发生改变,如何解决? vue更新数组时触发视图更新的方法
    vue中检测不到数组或者对象发生改变,如何解决? this.$set(对象/数组,键,值)Vue.set(对象/数组,键,值)给对象增加新属性、给数组增加属性都可以响应!this.$delete(对......
  • 差分约束笔记
    一个差分约束系统,是由多个形如\(x_i-x_j\leqc\)的不等式组成的。现在,我们要试图找出一组解,使得这些不等式都能被满足。我们在求最短路的过程中,用到一个和上面很像的式......
  • 方法引用-数组的构造器引用
    方法引用-数组的构造器引用ArrayBuilder接口Demo类......
  • 算法 玩转数据结构 2-4 数组中查询元素和修改元素
    1重点关注1.1toString方法范式参考coding 1.2coding 2课程内容coding 3Coding3.1coding看4packagecom.......