比線段樹慢但是簡潔
一維差值維護(hù)
對a數(shù)組進(jìn)行m次操作，每次在l~r上加不同的值，最后輸出ql~qr的區(qū)間和
cha[i]=a[i]-a[i-1];//差值cha[l]+=k,cha[r+1]-=k;//差值維護(hù)//那么m次操作后a[i]=∑cha[1~i];s[i]=∑a[1~i];ans=s[r]-s[l-1];二維差值維護(hù)
矩陣 左上角(x,y) 右下角(x2,y2)//此處需要畫圖幫助理解s[x][y]=s[x][y]+s[x-1][y-1]-s[x-1][y]-s[x][y-1];s[x][y]+=k; s[x][y2+1]-=k; s[x2+1][y]-=k; s[x2+1][y2+1]+=k;for (i=1; i<=n; i++) for (j=1; j<=n; j++) a[i][j]=a[i-1][j]+a[i][j-1] -a[i-1][j-1]+s[i][j];新聞熱點
疑難解答
