D. Non-zero Segments----前缀和

古城微笑少年丶 2022-11-19 07:38 138阅读 0赞

一维前缀和：

sum\[0\] = 0;

sum\[i\] = sum\[i-1\] + a\[i\]

以O(1)求出区间\[i,j\]的区间和     ![sum\[i,j\]=b\[j\]-b\[i-1\]][sum_i_j_b_j_-b_i-1];    // 注意减一

代码模板：

int sum[0] = 0;
     rep(i,i,n) sum[i] = sum[i - 1] + a[i];　　//O(n)
     while(m--)　　　　　　　　//O(m)
        {
            int L, R; scanf("%d%d", &L, &R);
            printf("%d\n", sum[R] - sum[L - 1]);
        }

二维前缀和：

待定。。。

一维前缀和例子：

Non-zero Segments

**原题链接：** [https://codeforces.com/contest/1426/problem/D][https_codeforces.com_contest_1426_problem_D]

求某个子区间的和，如果为0，插入任意值使之不为0

用一维前缀和的原因是：在O(n)时间内能实现简化，只要两个位置的前缀和相同，这两个位置的子串和为0

用map来记录，但是每次要清空：如果判断前边的子串和0，插入一个正无穷的或者负无穷的值，那么这个子串不可能为0，就不在需要之前算过的前缀和了，

因为它们记录的是之前的前缀和情况，而这一已经不可能为0，更新前缀和到当前位置，同时也需要更新map，原理和之前一样。

代码：

#include <bits/stdc++.h>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    #define rep(i,a,n) for(int i=a;i<=n;i++)
    using namespace std;
    const int maxn = 2e5+5;
    ll a[maxn],ans,sum;
    map<ll,bool>mp;
    
    int main()
    {	
    	int n;
    	cin >> n;
    	mp[0] = true;
    	rep(i,1,n)
    	{
    		cin >> a[i]; 
    		sum += a[i];
    		if(mp[sum])
    		{
    			ans ++;
    			mp.clear();
    			mp[0] = true;
    			sum = a[i];		
    		}
    		mp[sum] = true;
    	}
    	cout << ans << endl;
    	return 0;
    }

还需要注意的一点：\#define ios ios::sync\_with\_stdio(false);cin.tie(0); cout.tie(0);

时间缩短了很多！

![20210127203117249.png][]

原理：

[sum_i_j_b_j_-b_i-1]: https://private.codecogs.com/gif.latex?sum%5Bi%2Cj%5D%3Db%5Bj%5D-b%5Bi-1%5D
[https_codeforces.com_contest_1426_problem_D]: https://codeforces.com/contest/1426/problem/D
[20210127203117249.png]: /images/20221119/38d7457bab9640f585f28d1d2504c365.png