两种差分

• 差分一：求数列A的某一段A[i]到A[j]的和（频繁的求）
  • 普通做法就是一个一个加A[i~j]，这会导致产生一层内循环
  • 优化就是，提前构造S数列，求S[j]-S[i-1]，直接搞定
• 差分二：对数列A的某一段加上同一个值a（频繁的加）
  • 普通做法就是A[i~j]每一个都＋a，同样会产生内循环
  • 优化就是，A[i]+a，A[j+1]-a，先欠着A[i+1~j]的，等出了循环后，一起算。
  • 最后A[i] = A[i] +A[i+1]