【树状数组】段改动,点查询
数组 查询 树状 改动
2023-09-14 09:10:07 时间
利用差分,先得到一个差分序列(如:(1,2,3,5)的差分序列为(1,1,1,2))
当[i,j]段中全部数均加上数m时。在差分序列的i位置加上m,在j+1位置减去m就可以
求和利用树状数组
下面是pascal程序:
var a,fai:array[0..1000] of longint; c:char; n,i,x,y,f,m:longint; function lowbit(x:longint):longint; begin lowbit:=x and (-x); end; procedure modify(k,d:longint); begin while k<=n do begin fai[k]:=fai[k]+d; k:=k+lowbit(k); end; end; function sum(x:longint):longint; begin sum:=0; while x>0 do begin sum:=sum+fai[x]; x:=x-lowbit(x); end; end; begin readln(n); for i:=1 to n do begin read(a[i]); modify(i,a[i]-a[i-1]); end; readln(m); for i:=1 to m do begin read(c); if c='C' then begin readln(x,y,f); modify(x,f); modify(y+1,-f); end; if c='Q' then begin readln(x); writeln(sum(x)); end; end; readln; end.
相关文章
- springMVC接受对象集合,name数组
- 树状数组的区间修改与查询
- js判断数组中是否包含某个指定元素的个数_js 数组包含某个元素
- jQuery将数组转化成对象
- Java数组、排序和查找
- 将string数组转化为sql的in条件用sql查询
- JAVASCRIPT如何判断数组中有重复内容详解编程语言
- 删除排序数组中的重复项算法详解编程语言
- PHP实现查询两个数组中不同元素的方法详解编程语言
- PHP rsort():数组排序(降序)
- MySQL数组查询:解锁更多功能(mysql数组查询)
- 利用Oracle数组实现快速查询(oracle数组查询)
- MySQL中使用数组字段的技巧(mysql数组字段类型)
- MySQL查询:返回一个数组(mysql查询返回数组)
- 优化Oracle存储数组的方法(oracle存储数组)
- 「MongoDB技巧解密」:快速精确实现数组查询(mongodb数组查询)
- Oracle实现多参数传递数组的方法(oracle 传递 数组)
- Redis实现数组快速查询(redis 查询数组)
- 计算100000数组js脚本的执行时间
- php下几个常用的去空、分组、调试数组函数
- JavaScript中的稀疏数组与密集数组[译]
- 将string数组转化为sql的in条件用sql查询
- 关于JS数组追加数组采用push.apply的问题
- thinkphp数据查询和遍历数组实例