perogram

二次元累積和は1-indexedで。--No.755 Zero-Sum Rectangle--

Quiz

https://yukicoder.me/problems/no/755

AC Code

https://yukicoder.me/submissions/353176

解法

  • 二次元累積和

その他

  • 1-indexedで考えて、添字0の箇所は0で埋めておくと、sumを求めるときの引き算が統一的に扱えるのでバグりにくい
ll sum = A[x1][y1] - A[x0-1][y1] - A[x1][y0-1] + A[x0-1][y0-1];

f:id:peroon:20190621052002j:plain

  • (0-indexedで考えると、x0==0のときはA[x0-1][y1]を引いてはいけない、など考慮しなければいけなくなる)

二次元累積和を使う他の問題