精华内容
下载资源
问答
  • 前缀和

    千次阅读 多人点赞 2020-03-12 15:40:25
    前缀和】 什么是前缀和?前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。 设b[]为前缀和数组,a[]为原数组,根据这句话可以得到前缀和的定义式和递推式: 定义式 递推式 一维前缀...

    【前缀和】

    什么是前缀和?前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。 

    设b[]为前缀和数组,a[]为原数组,根据这句话可以得到前缀和的定义式和递推式:

      定义式 递推式
    一维前缀和  b[i]=\sum_{j=0}^{i}a[j] b[i]=b[i-1]+a[i]
    二维前缀和 b[x][y]=\sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j] b[x][y]=b[x-1][y]+b[x][y-1]-b[x-1][y-1]+a[x][y]

     

    【一维前缀和】

    根据上面的定义,我们可以很容易得到 sum[i] = sum[i-1] + a[i]   这样就可以得到前i个数的和

    根据上述表达式我们可以以O(1)求出区间[i,j]的区间和     sum[i,j]=b[j]-b[i-1]

     

     

    代码:

    #include <cstdio>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstdbool>
    #include <string.h>
    #include <math.h>
    
    using namespace std;
    
    
    
    int main()
    {
        int a[100005] = {0};
        int b[100005] = {0};
        int n;
        cin >> n;
        for (int i=1;i<=n;i++)
        {
            cin >> a[i];
            b[i] = b[i-1] + a[i];
        }
        int t;
        cin >> t;
        while (t--)
        {
            int l,r;
            int sum = 0;
            cin >> l >> r;
            sum = b[r] - b[l-1];
            printf("%d\n",sum);
        }
        return 0;
    }

     

    这道题改动了一下,如果可以找到,那么输出所有的符合条件的区间

    这道题的思路其实不难理解:

    例如:

    [1,a] 和 [1,b]   (b > a)

    如果要满足条件那么  (b-a) % m == x

    ->           (b-x) % m == a

    我们对它的前缀和对m模(假设为 t )并存储

    vis[(t-x+m)%m] 存在,则说明可以找到这样的一个子区间

    但是由于我这里要输出所有的符合条件的区间,所以我需要去存储数组索引 (也就是区间的左边界)

    一种是利用二维数组:

    #include <cstdio>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstdbool>
    #include <string.h>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
        int n,m,x;
        cin >> n >> m >> x;
        int ss[105][105];
        for (int i=0;i<105;i++)
        {
            for (int j=0;j<105;j++)
            {
                ss[i][j] = -1;
            }
        }
        int a[105];
        int vis[105] = {0};
        int pre[105];
        pre[0] = 0;
        ss[0][0] = 0;
        int l,r;
        for (int i=1;i<=n;i++) {
            cin >> a[i];
        }
        for (int i=1;i<=n;i++){
            pre[i] = (pre[i-1] + a[i]) % m;
            vis[pre[i]]++;
            int xh = (pre[i] - x) % m;
            if (xh < 0)
                xh += m;
            if (vis[xh] != 0)
            {
                for (int j=0;j<105;j++)
                {
                    if (ss[xh][j] != -1)
                    {
                        l = ss[xh][j] + 1;
                        r = i;
                        cout << l << " " << r << endl;
                    } else
                        break;
                }
            }
            for (int j=0;j<105;j++)
            {
                if (ss[pre[i]][j] == -1)
                {
                    ss[pre[i]][j] = i;
                    break;
                }
                else
                    continue;
            }
        }
        return 0;
    }

    一种是利用vector:

    #include <cstdio>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstdbool>
    #include <string.h>
    #include <math.h>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        int n;
        int m;
        int x;
        scanf("%d%d%d", &n, &m, &x);
        int a[100];
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
    
        int pre[100];
        pre[0] = 0;
    
        vector<int> preffix[100];
        preffix[0].push_back(0);
        for (int i = 1; i <= n; ++i) {
            pre[i] = (pre[i-1] + a[i]) % m;
    
            int xh = (pre[i] - x) % m;
            if (xh < 0) { xh += m; }
    
            if (!preffix[xh].empty()) {
                for (int pre_index: preffix[xh]) {
                    printf("%d:%d\n", pre_index + 1, i);
                }
            }
    
            preffix[pre[i]].push_back(i);
        }
    
        return 0;
    }

     

    直接在问题二的基础上修改就可以了

     

     

    思路:

    因为是除去区间[l,r] 那么我就分两个前缀和(一个从前往后求,一个从后往前求)

    pre[l-1] 和 suf[r+1] 求这俩的gcd就可以了

     

    代码:

    #include <cstdio>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstdbool>
    #include <string.h>
    #include <math.h>
    #include <vector>
    
    using namespace std;
    
    int pre[10005];
    int suf[10005];
    int a[100005];
    int n;
    int gcd(int a,int b)
    {
        return b ? gcd(b, a % b) : a;
    }
    
    void presolve()
    {
        pre[0] = 0;
        for(int i = 1; i <= n; i++) {
            pre[i] = gcd(pre[i - 1], a[i]);
        }
        suf[n + 1] = 0;
        for(int i = n; i >= 1; i--) {
            suf[i] = gcd(suf[i + 1], a[i]);
        }
    }
    
    int query(int l,int r)
    {
        return gcd(pre[l-1],suf[r+1]);
    }
    
    int main()
    {
        cin >> n;
        for (int i=1;i<=n;i++)
            cin >> a[i];
        presolve();
        int l,r;
        cin >> l >> r;
        int n_gcd = query(l,r);
        printf("%d\n",n_gcd);
        return 0;
    }

     

    【问题五】

    给你一串长度为n的数列a1,a2,a3......an,要求对a[L]~a[R]进行m次操作:

    操作一:将a[L]~a[R]内的元素都加上P

    操作二:将a[L]~a[R]内的元素都减去P

    最后再给出一个询问求a[L]-a[R]内的元素之和?

     

     这里讲差分! 

    它可以用来专门解决这种修改值的问题!

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+9;
    int a[maxn],b[maxn];
    int main(){
        int i,j,k,n,m,p;
        cin>>n>>m;
        for(i=1;i<=n;i++){
            cin>>a[i];
        }
        for(i=1;i<=m;i++){
            int L,R,t;
            cin>>t>>L>>R>>p;
            if(t==1){
                b[L]+=p;b[R+1]-=p; //仔细想想为什么b[R+1]要减去p
            }
            else{
                b[L]-=p;b[R+1]+=p;
            }
        }
        int add=0;
        for(i=1;i<=n;i++){
            add+=b[i];
            a[i]+=a[i-1]+add;
        }
        int x,y;
        cin>>x>>y;
        cout<<a[y]-a[x-1]<<endl;
    }

    为什么操作一时b[R+1]要减去p,很简单,因为操作一我只需对[L,R]区间里的数加p,[R+1,n]这个区间里的数没必要加p,所以需要减掉p。

     

     

    【二维前缀和】

    DP[i][j]表示(1,1)这个点与(i,j)这个点两个点分别为左上角和右下角所组成的矩阵内的数的和,好好想一下状态转移方程,DP[i][j]=DP[i-1][j]+DP[i][j-1]-DP[i-1][j-1]+map[i][j],怎么来的呢?我们画一下图就知道了。

    这张图就知道了(i,j)可以由(i-1,j)和(i,j-1)两块构成,不过要注意两个点,1、有一块矩阵我们重复加了,也就是(i-1,j-1)这一块,所以我们要减去它。2、我们这个矩阵是不完整的,由图可知我们还有一块深蓝色的没有加,也就是(i,j)这一点,所以我们要再加上map[i][j]也就是题目给出的矩阵中这一格的数。
     

    如果我们定义[x1,y1] 为所求矩阵左上角 [x2,y2] 为所求矩阵右下角   如何得到它们所围成矩阵的总和呢?

    我们可以通过DP[x2][y2]来计算,我们通过图可以发现这个距离我们要的还差红色的部分看看怎么表示红色部分?我们可以分割成两块,分别是DP[x1][y2]和DP[x2][y1]我们发现有一块重复减了,所以我们再加上它即DP[x1][y1],有一点注意,因为画图和定义原因我们发现边界好像不对,我们来看看,我们定义的状态是整个矩阵包括边的和,而我们要求的也是要包括边的,所以我们要再改一下,把DP[x1][y2]和DP[x2][y1]和DP[x1][y1]分别改成DP[x1-1][y2]和DP[x2][y1-1]和DP[x1-1][y1-1]这样一减我们就可以得到自己想要的答案,整理可得公式,DP[x2][y2]-DP[x1-1][y2]-DP[x2][y1-1]+DP[x1-1][y1-1]这样我们就可以做到O(1)之内查询
     

    求前缀和的代码:

    #include<iostream>
    #include<cstring>
    using namespace std;
    int dp[2000][2000],map[2000][2000];
    int main()
    {
        int m,n,k;//所给的矩阵是n*m的,有k组查询 
        cin >>n>>m>>k;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >>map[i][j];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)//预处理一波 
            for(int j=1;j<=m;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
        for(int i=1;i<=k;i++)//接受查询 
        {
            int x1,x2,y1,y2;
            cin >>x1>>y1>>x2>>y2;
            cout <<(dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1])<<endl;//O(1)查询 
        }
        return 0;
    } 

     

    展开全文
  • 前缀和、二维前缀和与差分的小总结

    万次阅读 多人点赞 2018-08-17 16:21:35
    在了解二维前缀和之前,我们首先需要了解一下什么是前缀和。 如果我给你一串长度为n的数列a1,a2,a3......an,再给出m个询问,每次询问给出L,R两个数,要求给出区间[L,R]里的数的和,你会怎么做,若是没有了解过前缀...

    在了解二维前缀和之前,我们首先需要了解一下什么是前缀和。

    如果我给你一串长度为n的数列a1,a2,a3......an,再给出m个询问,每次询问给出L,R两个数,要求给出区间[L,R]里的数的和,你会怎么做,若是没有了解过前缀和的人看到这道题的想法可能是对于m次询问,我每次都遍历一遍它给的区间,计算出答案,这样子的方法固然没错,但是其时间复杂度达到了O(n*m),如果数据量稍微大一点就有可能超时,而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大节省了运算时间。至于怎么用,请看下面一小段代码

    a[0]=0;
    
    for(int i=1;i<=n;i++)a[i]+=a[i-1];

    没错,前缀和顾名思义就是前面i个数的总和。数组a在经过这样的操作之后,对于每次的询问,我们只需要计算a[R]-a[L-1]就能得到我们想要的答案了,是不是很简单呢。

    在知道了最简单的前缀和之后,我们再来了解一下什么是差分。

    给你一串长度为n的数列a1,a2,a3......an,要求对a[L]~a[R]进行m次操作:

    操作一:将a[L]~a[R]内的元素都加上P

    操作二:将a[L]~a[R]内的元素都减去P

    最后再给出一个询问求a[L]-a[R]内的元素之和?

    你会怎么做呢?你可能会想,我对于m次操作每次都遍历一遍a[L]~a[R],给区间里的数都加上P或减去P,最后再求一次前缀和就行了。没错,这样子确实也能得出正确答案,但时间复杂度却高达O(M*n),对于1<=n,m<=1e5这个数据范围来说直接就tle了,所以说这个方法不可行。既然这样不行的话,那我们要怎么做才能快速的得到正确答案呢?是的,这个时候我们的差分就该派上用场了,我们新开一个数组b,储存每一次的修改操作,最后求前缀和的时候统计一下就能快速的得到正确答案了,详细请看下面代码。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+9;
    int a[maxn],b[maxn];
    int main(){
    	int i,j,k,n,m,p;
    	cin>>n>>m;
    	for(i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	for(i=1;i<=m;i++){
    		int L,R,t;
    		cin>>t>>L>>R>>p;
    		if(t==1){
    			b[L]+=p;b[R+1]-=p; //仔细想想为什么b[R+1]要减去p 
    		}
    		else{
    			b[L]-=p;b[R+1]+=p;
    		}
    	}
    	int add=0;
    	for(i=1;i<=n;i++){
    		add+=b[i];
    		a[i]+=a[i-1]+add;
    	}
    	int x,y;
    	cin>>x>>y;
    	cout<<a[y]-a[x-1]<<endl;
    }

    相信看到这里,大家已经仔细思考过代码了,为什么操作一时b[R+1]要减去p,很简单,因为操作一我只需对[L,R]区间里的数加p,[R+1,n]这个区间里的数没必要加p,所以需要减掉p。

    差分讲解完毕,接下来我们终于要开始今天的正题——二维前缀和了。

    还是以小问题的形式来讲解二维前缀和吧。

    给定一个n*m大小的矩阵a,有q次询问,每次询问给定x1,y1,x2,y2四个数,求以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素和。注意仍然包含左上角和右下角的元素。

    怎么做呢?为了方便你们理解,我画个图吧。

    图画的很丑,希望不要介意。如图所示,按题目要求,我们每次要求的答案就是红色圆圈所在的区域的值(注意,这里的x1,x2表示行,y1,y2表示列),对比上面这张图我们能够发现红色区域的值等于四个区域的值减去(白色区域+黑色区域),再减去(白色区域+蓝色区域),最后因为白色区域被减了两次,我们需要再加回来。所以ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];(注意,此时的a数组代表的是前缀和)。突然想起来还没说怎么求二维前缀和,很简单,看下面代码。

    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++)
    	a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    } 

    为方便理解贴个图

    假如我想求a[2][4]的前缀和,我得先加上a[1][4]的前缀和,再加上a[2][3]的前缀和,然后这个时候我们发现实际上a[1][3]这个部分我们加了两遍,所以我们需要再减去一遍a[1][3],于是得出公式a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]

    接下来看完整代码吧。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e3+9;
    int a[maxn][maxn];
    int main(){
    	int i,j,k,n,m,q;
    	cin>>n>>m>>q;
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++)
    		cin>>a[i][j];
    	}
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++)
    		a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    	}
    	for(i=1;i<=q;i++){
    		int x1,y1,x2,y2;
    		cin>>x1>>y1>>x2>>y2;
    		int ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
    		cout<<ans<<endl;
    	}
    }

    是不是感觉很简单呢,哈哈哈哈哈哈哈。

    在学完二维前缀和之后,一些同学可能会有疑问,一维前缀和能用上差分,那么二维前缀和能不能用上差分呢?答案是肯定的。

    那么怎么差分呢?方法是和一维类似的,我们也是需要另开一个数组记录修改操作,最后求前缀和时统计修改操作,只是二维每一次操作需要记录4个位置,一维只需要记录2个位置。具体怎么做,看下面代码吧。

    for(int i=0;i<m;i++){//m是修改操作次数 
    	int x1,y1,x2,y2,p;
    	cin>>x1>>y1>>x2>>y2>>p;
    	b[x1][y1]+=p;b[x2+1][y2+1]+=p;
    	b[x2+1][y1]-=p;b[x1][y2+1]-=p;
    }

    好了,一维前缀和、二维前缀和、差分都说完了,希望看这篇文章的人能够有所收获吧。

    展开全文
  • 前缀和——(1)什么是前缀和和一维前缀和

    千次阅读 多人点赞 2019-12-13 12:32:40
    什么是前缀和 前缀和(Prefix Sum)的定义为:对于一个给定的数列 A, 它的前缀和数列 S 是通过递推能求出来得 部分和。 例如: C++实现 //假设数组a和前缀和数组s都已经定义 int i; //初始条件 a[0] = 0; s[0...

    什么是前缀和

    前缀和(Prefix Sum)的定义为:对于一个给定的数列 A, 它的前缀和数列 S 是通过递推能求出来得 S[i] = \sum_{j = 1}^{i}A[j]  部分和。

    例如:

    A[5, 6, 7, 8] = PrefixSum[5, 11, 18, 26]\\ PrefixSum[0] = A[0]\\ PrefixSum[1] = A[0] + A[1]\\ PrefixSum[2] = A[0] + A[1] + A[2]\\ PrefixSum[3] = A[0] + A[1] + A[2] + A[3]\\ ...\\ PrefixSum[n] = A[0] + A[1] + A[2] + A[3] + ... + A[n]

    C++实现

    //假设数组a和前缀和数组s都已经定义
    int i;
    //初始条件
    a[0] = 0;
    s[0] = 0;
    for (i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }

    模板题

    下面我们用一个模板题,将完整的一维数组前缀和做一个简单的展示。题目链接http://47.110.135.197/problem.php?id=5181

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main() {
    	int n;
    	cin >> n;
    	
    	int data;
    	int ans[102] = {};
    	for (int i=1; i<=n; i++) {
    		cin >> data;
    		ans[i] = ans[i-1] + data;
    	}
    	
    	for (int i=1; i<=n; i++) {
    		cout << ans[i] << " ";
    	}
    	cout << endl;
    	
    	return 0;
    }

    用途

    前缀和是一种重要的预处理,能大大降低查询的时间复杂度。

    前缀和是以求和的方式灵活地面对区间询问。

    下面我们用一个模板题来说明。

    例题:区间求和

    给你一串长度为 n 的数列 a1, a2, a3, ..., an,再给出 m 个询问,每次询问给出 L, R 两个数,要求给出区间 [L, R] 里的数的和。

    详细可以参看http://47.110.135.197/problem.php?id=5139

    题目分析

    题目非常简单,我们也可以得到一个最简单的解法,暴力操作。也就是对应每个询问,我们都从 L 开始到 R 结束对这个区间的数据进行求和。基本的代码如下:

    #include <iostream>
    
    using namespace std;
    
    const int MAXN = 1e5+2;
    long long arr[MAXN] = {};
    
    int main() {
        int n;
        cin >> n;
        
        int i, j;
        for (i=1; i<=n; i++) {
            cin >> arr[i];
        }
    
        int m;
        int l, r;
        long long ans = 0;
        cin >> m;
        for (i=0; i<m; i++) {
            cin >> l >> r;
    
            ans = 0;
            for (j=l; j<=r; j++) {
                ans += arr[j];
            }
    
            cout << ans << endl;
        }
    
        return 0;
    }

    代码分析

    从上面的代码非常明确的分析出来,代码的时间复杂度为 O(n * m)。也就是说,在比赛中这样的解法能否 AC,那就要看数据的量了。当然我们都知道这样的解法,比赛中是肯定不可能 AC。因此唯一的可能就是降低时间复杂度。方法就是使用前缀和。

    我们先看前缀和的数学。数列A中某个下标区间 [l, r] 内的数的和定义为:

    sum[l, r] = \sum_{i = l}^{r}A[i]\\ = a[l] + a[l+1] + \cdots + a[r]\\ = S[r] - S[l-1]

    从上面推导,我们可以清晰的看出,前缀和和区间和的关系。

    代码改进

    #include <iostream>
    
    using namespace std;
    
    const int MAXN = 1e5+2;
    long long arr[MAXN] = {};
    long long sum[MAXN] = {};
    
    int main() {
        int n;
        cin >> n;
        
        int i, j;
        for (i=1; i<=n; i++) {
            cin >> arr[i];
            sum[i] = sum[i-1] + arr[i];
        }
    
        int m;
        int l, r;
        cin >> m;
        for (i=0; i<m; i++) {
            cin >> l >> r;
            cout << sum[r] - sum[l-1] << endl;
        }
    
        return 0;
    }

    代码分析

    从上面的代码非常明确的分析出来,代码的时间复杂度为 O(n)

    展开全文
  • 【一维前缀和】 给定一个数组A[1,2,……n],则它的前缀和数组为PrefixSum[1..n]。定义为:PrefixSum[i] = A[0]+A[1]+...+A[i-1]; 【例子】 A[5,6,7,8] --> PrefixSum[5,11,18,26] PrefixSum[0] =A[0] ; ...

    前缀和是一种重要的预处理,能大大降低查询的时间复杂度。

    【一维前缀和】

    给定一个数组A[1,2,……n],则它的前缀和数组为PrefixSum[1..n]。定义为:PrefixSum[i] = A[0]+A[1]+...+A[i-1];

    【例子】

    A[5,6,7,8] --> PrefixSum[5,11,18,26]

    PrefixSum[0] =A[0] ;

    PrefixSum[1] =A[0] + A[1] ;

    PrefixSum[2] =A[0] + A[1] + A[2] ;

    PrefixSum[3] =A[0] + A[1] + A[2] + A[3] ;

    【用法】

    1. 可以通过前缀和求出任意区间的求和值,比如我们想求出[5,10]区间内的求和值,即s[10]-s[4]=[5,10]

    【二维前缀和】

    从上图中可以看出,前缀和数组里每一个位置都表示原数组当前index左上方的数字的和。
    比如像图里面画的:prefixSum[3, 3] = src[0~2, 0~2]的和;
    二维前缀和数组要怎么计算出来呢?
    可以分为四种情况

    1. i==0 && j==0,只有一个直接赋值即可:prefixSum[0, 0] = src[0, 0]。
    2. i==0,最左边的一排,图中黄色部分,prefixSum[0, j] = prefixSum[0, j-1] + src[0, j];
    3. j==0,最上面一排,途中红色部分,prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];
    4. i!=0 || j!=0,图中绿色部分,prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];


    我们要得到prefixSum[2,2],我们知道应该是图一中箭头指向的区域。也就是9个方框加起来的和,也就是54。
    看图二,我们可以利用prefixSum[1, 2]和prefixSum[2, 1],但是他俩的区域是重合的,如图二所示,重合的区域又恰好是prefixSum[1, 1]负责的区域,相当于加了两份,需要减掉一份。
    所以prefixSum[2,2] = prefixSum[1, 2] + prefixSum[2, 1] - prefixSum[1, 1] + src[2, 2];
    也就是54 = 33 + 21 -12(这个是prefixSum[1, 1]) +12(这是src[2, 2])

    
            for (int i = 0; i < src.length; i++) {
                for (int j = 0; j < src[0].length; j++) {
                    if (i == 0 && j == 0) {//第0个,最左上角
                        result[i][j] = src[i][j]
                    } else if (i == 0) {//第一行,最顶部一行
                        result[i][j] = result[i][j - 1] + src[i][j]
                    } else if (j == 0) {//第一列,最左边一列
                        result[i][j] = result[i - 1][j] + src[i][j]
                    } else {//其他
                        result[i][j] = result[i - 1][j] + result[i][j - 1] + src[i][j] - result[i - 1][j - 1]
                    }
                }
            }
            return result;

     

    展开全文
  • 前缀和前缀积

    2019-08-19 10:07:04
    1.前缀和,每一项b[i]为a[0]+a[1]+a[2]…a[i]的和 2.前缀积,每一项b[i]是a[0]*a[1]…a[i]的积 类似还有后缀积,后缀和等。 求前缀积的方法: for(int i = 0; i < n; i++) b[i] = a[i] * ((i == 0) ? 1 : b [i -...
  • 前缀和——(3)树上前缀和

    千次阅读 2020-01-01 20:49:24
    前面部分我们介绍了一维前缀和...下面我们简单介绍一下树上前缀和。 什么是树上前缀和 假设表示结点 i 到根节点的权值总和。 然后若是点权,路径上的和为; 否...
  • 关于前缀与前缀和

    2018-08-11 20:26:32
    前缀: 如一个序列:1,2,3,4,5,6,那么5的前缀:1;...还是上面的序列,那么5的前缀和:1+2+3+4=10;即该数前所有数的和; 求某个数的前缀和,即sum[ j ] - sum[ j -1 ];时间复杂度为O(1);...
  • 【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用

    千次阅读 多人点赞 2021-05-31 09:12:12
    【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用 文章目录【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用在区间范围内统计奇数数目★区域和检索 - 数组不可变★★子数组异或查询★★定长子串中元音的最大数目★★生存...
  • 前缀和——(2)二维数组前缀和

    千次阅读 2019-12-30 09:54:42
    下面我们扩展一下,来介绍二维前缀和。 什么是二维前缀和 比如我们有这样一个矩阵a,如下所示: 1 2 4 3 5 1 2 4 6 3 5 9 我们定义一个矩阵sum,其中,那么这个矩阵就是这样的: 1 3 7 10 6 9 15 22...
  • 矩阵前缀和

    2019-09-15 10:50:38
    今天在学习的过程总,遇到了以前曾经学到的前缀和,不过这个稍微复杂一点,二维数组的前缀和,也可以说是矩阵前缀和 一维数组中转变为前缀和数组之后,每一行就代表着前几项的总和,同理前缀和矩阵中每一个元素代表...
  • 前缀和讲解

    千次阅读 2019-01-23 20:52:19
    什么是前缀和? 假如有一个数组 a[0]、a[1]、a[2]、a[3]、...、a[n] 令 s[i]=a[0]+a[1]+...+a[i]//数组前i项和=&gt;区间[0,i]之间的所有和=&gt;i的前缀和 此时的s就是数组的一维前缀和 前缀和是一种比较重要...
  • 前缀和 什么是前缀和   前缀和顾名思义就是指一个数组的某一个下标的(包括该下标)之前的所有数组元素的和。现在我们假设有某一数组a = [1, 2, 3, 4, 5, 6, 7, 8, 9]。其前缀和数组为sum,那么sum数组与a数组对应...
  • 前缀和算法

    2020-05-10 17:59:10
    思路:差分前缀和求出每个数字被查询的次数,然后sort排序,一次赋值n到1,最大的对应n #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm>...
  • 前缀和概述

    千次阅读 2017-10-26 19:57:03
    某个元素k的前缀是指从第一个元素a到元素k前面的元素b,了解了前缀的概念以后,正式进入前缀和的话题。    ———- 2.有趣的前缀和  还是这个栗子:  1234567这一串数字,那么"4"这个元素的...
  • 前缀和问题

    2018-08-29 00:12:48
    利用前缀和保存得到前缀和数组,并用一个数组记录下此时前缀和出现的次数,因为当重复出现同一个前缀和的时候代表有一段区间能够%k==0。 代码: #include &lt;math.h&gt; #include &lt;algorith...
  • C语言前缀和

    千次阅读 2018-11-28 21:33:37
    前缀和后缀是什么呢? 举个例子: +34 3+4 34+ 前缀 中缀 后缀 也称为: 波兰式 逆波兰式 --------------------- 那就以 X=A+B*(C-D)/E 为例: 先转换成前缀表达式 第一步:先加括号:(X=(A + ( ( ...
  • 前缀和技巧

    2020-03-06 13:55:13
    前缀和技巧 先看一道题 一道简单却十分巧妙的算法问题:算出一共有几个和为 k 的子数组。 那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 k 不就行了。关键是,如何快速得到某个子数组的和呢,比如说给你...
  • 前缀和思想

    2018-08-26 12:32:52
    一个区间可以拆成两个前缀和,这是一个很基本的思想。 反过来,两个前缀和的关系可以由一个区间表示。。。 有时某些区间问题可以转化为前缀和问题继而减少情况和状态。。 例: 魔术师的桌子上有n个杯子排成一行...
  • 高维前缀和

    千次阅读 2018-11-22 19:51:23
    高维前缀和就是求关于一个集合子集(或超集)的状态的和 牛客有一道题写的很好 传送门 题面就已经说明了高维前缀和的原理 链接:https://ac.nowcoder.com/acm/contest/167/C 来源:牛客网 对于一个一维数组求部分和,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,482
精华内容 22,592
关键字:

前缀和