連続して〇〇を除く
例えば「ある1つを除いた時のそれ以外の〇〇を計算」系では、左からの累積〇〇と、右からの累積〇〇を組み合わせることで効率的に計算することができる。前計算O(N)でそれぞれがO(1)で処理、みたいなのだと次元が1つ落とせます。
それと同じ考え方で、「ある連続するものを除いた時のそれ以外の〇〇を計算」するのもできる。
https://gyazo.com/7e3cd23fce6949826ea69b599c3bc95c
C - GCD on Blackboard
E - All-you-can-eat
#累積