前綴和是一種預處理技巧,通過構建前綴和數組,可以在O(1)時間內計算任意區間的和。 原理 原數組: [a₀, a₁, a₂, …, aₙ] 前綴和: prefix[i] = a₀ + a₁ + … + aᵢ₋₁ 區間和: sum(i, j) = prefix[j+1] - prefi