前綴和：前綴和數組如何快速計算區間和？

前綴和數組是一種用於快速計算區間和的輔助數組。定義爲：原數組A的前綴和數組S，其中S[0]=0，S[k]（k≥1）是A[1]到A[k]的和，即S[k] = S[k-1] + A[k]。例如原數組A=[1,2,3,4,5]，其前綴和數組S=[0,1,3,6,10,15]。 計算區間和的核心公式是：原數組從第i個到第j個元素的和 = S[j] - S[i-1]。例如計算A[2]到A[4]的和，用S[4]-S[1]=10-1=9，結果正確。 優勢在於：預處理S數組需O(n)時間，每次區間和查詢僅需O(1)時間，總複雜度O(n+q)（q爲查詢次數），遠快於直接計算的O(qn)。需注意索引對齊（如原數組從0開始時公式調整）、區間合法性及空間換時間的特點。 前綴和數組通過“提前累積”實現