前綴和

前綴和定義；s[0]=0; s[i]=s[i-1]+a[i]; 其中s[i]數組為a[i]數組的前綴和；

有了前綴和后，給定一個區間 [l,r] 的和就可以表示為；
sum=s[r] -s[l-1];

代碼：

cin >> n >> m ;s[0] = 0;for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];//求前綴和bool re = true;for (int i = 1; i <= m; i++){unsigned long long x = l[i], y = r[i];unsigned long long sum = s[y] - s[x - 1];if (re){re = false;ans = sum;}elseans =ans^ sum;}

差分

對于一個給定的數列A,它的差分數列B定義為:

B[1]=A[1,B[]=A[i]-A[t-1(2≤i≤n)
容易發現,“前綴和”與“差分”是一對互逆運算,差分序列B的前綴和序列就是
原序列A,前綴和序列S的差分序列也是原序列A
把序列A的區間[l,r]加d(即把A,A+1,…,A都加上d),其差分序列B的變
化為B[l]加d,B[r+1]減d,其他位置不變。這有助于我們在很多題目中,把原序列上
的“區間操作”轉化為差分序列上的“單點操作”進行計算,降低求解難度。

代碼：

cin >> n >> m >> seed;s[1] = a[1];for (int i = 2; i <= n; i++)//差分s[i] = a[i] - a[i - 1];s[n + 1] = 0;for (int i = 1; i <= m; i++){int L = l[i], R = r[i], q = p[i];s[L] -= q, s[R + 1] += q;//差分}a[1] = s[1];for (int i = 2; i <= n; i++)//前綴和a[i] = a[i - 1] + s[i];for (int i = 1; i <= n; i++){if (a[i] < 0)a[i] = 0;ans = ans ^ a[i];}cout << ans << endl;return 0;

總結

以上是生活随笔為你收集整理的前缀和与差分的使用（新手快速入门）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。