01.前缀和

概念：前缀和是指在一个数列中，以某个数字作为前缀的数字和

一维数组一维前缀和数组模板  sum[0]=arr[0];           i=0  sum[i]=sum[i-1]+arr[i];  i>0
int arr[5] = {2,3,5,7,11};  int sum[5];  for(int i = 0;i < 5;i++)  {          if(i == 0)              sum[i] = arr[i];          else              sum[i] = sum[i-1] + arr[i];  }  //输入sum数组验证  for(int i = 0;i < 5;i++)      cout << sum[i] << " ";    //输入2 5 10 17 28

作用：求区间[l,r]内的数组和

区间[l,r]的和 = arr[l]+arr[l+1]+...arr[r-1]+arr[r];sum[r]-sum[l-1] = sum[0]+sum[1]+...sum[l-2]+sum[l-1]+sum[l]+...sum[r]                - sum[0]+sum[1]+...sum[l-2]+sum[l-1]                =sum[l]+...sum[r]由此可得，当求一个数组在区间[l,r]内的和，咱们能够用它的前缀和和数组疾速得出答案