检查数组是一种数据结构。 相当于与前缀的逆运算。
检查数组的功能是修改区间、查询点。
修正区间的时间复杂度为o(1)。
查询点的时间复杂度为o(n )。 如果能根据树阵列的时间复杂度来达成o(logn )的话。
修正区间操作
x位置加上修正量，从y 1位置减去修正量。 这样就修正了整个区间的要素。 staticvoidupdate(intx，int y，int z ) {b[x]=z； b[y 1]-=z； }查询
修改变得方便了，但查询时需要全部添加。 静态Intsum (intx ) {int ans=0； for(intI=1； i=x； I ) ans=b[i]； 返回Ans； }预处理b[1]=a[1]； for(intI=2； i=n； I ) b(I )=a(I )=a(I-1 )； 从算法上建立搜索分配序列s。 使用递归公式：c[i]=a[i-1]-a[i]。
s[left] k，s[right 1]-k可以达到区间修正的目的。
单点查询：求前缀和。
如何恢复原始数组： s[i]=s[i-1]
D - Tallest Cow原题链接
这个问题的数据卡很死。 这个方法应该不是最佳的。 我在原题中提到的最大数据范围内打开了数组空间。 然后超过了内存。
import java.io.IOException； import java.util.Scanner； 公共类主{/* * poj-3263 d-tallest cow *数组前缀和*/static int N，I，r，h，a，b，m，cf[]； 静态布尔vis [ ] [ ]； publicstaticvoidmain (字符串[ ] args ) throwsioexception ) scannersc=newscanner(system.in )； N=sc.nextInt (； I=sc.nextInt (； H=sc.nextInt (； R=sc.nextInt (； M=N 1； vis=new boolean [M][M]； cf=new int [N 1]； for(intI=1； i=R； I () {a=sc.nextInt )； b=sc.nextInt (； if(ab ) { int temp=a； a=b； b=temp； (if (！ vis[a][b]}{cf[a1]----； cf[b]； vis[a][b]=true； }}int res=0； for(intI=1； i=N； I ) {res=cf[i]； system.out.println(HRES； }//*93551353433798545344555/