前缀和与差分

二维前缀和

P2280 [HNOI2003]激光炸弹 

https://www.luogu.org/problemnew/show/P2280

 1 FOR(i,1,n) 
 2 {
 3     int x,y,v;
 4     cin>>x>>y>>v;
 5     s[x+1][y+1]=v;
 6 }
 7 FOR(i,1,5001) FOR(j,1,5001) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; 
 8 FOR(i,0,5000-r) FOR(j,0,5000-r)
 9     ans=max(ans,s[i+r][j+r]-s[i][j+r]-s[i+r][j]+s[i][j]);
10 cout<<ans;

差分：现修改，后询问，总复杂度O(n)

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/universeplayer/p/10655342.html