精华内容
参与话题
问答
  • 前缀和与差分

    千次阅读 2019-03-22 22:35:50
    前缀和:新建一数组B,数组中每一项B[i]保存A中[0…i]的和; 后缀和:新建一数组B,数组中每一项B[i]保存A中[i…n-1]的和; 前缀积:新建一数组B,数组中每一项B[i]保存A中[0…i]的积; 后缀积:新建...

    前缀和是一种极其优秀的线性结构,也是一种重要的思想,能极大地降低区间查询的时间复杂度。

    前缀和数组的下标一般从 11 开始。

    1. 一维前缀和

    1.1 原理

    问题描述:假设有一串长度为 nn 的序列 {a1,a2,a3......an}\left\{ a_1, a_2, a_3 ...... a_n \right\},给出 mm 次询问,每次询问给出 L,RL, R 两个数,求区间 [L,R][L,R] 的和。

    如果使用暴力解法,每次都遍历一遍给出的区间,计算出答案,这样时间复杂度会达到 O(nm)O(n*m),极有可能会 TLE。

    使用前缀和来做的话,能将时间复杂度降到 O(n+m)O(n+m),极大地减少了时间。

    前缀和数组的第 ii 项就是一个序列前面 ii 个数的总和,求法如下:

    void init()
    {
        sum[0] = 0;
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + a[i];
    }
    

    对于已经求出的前缀和,区间 [L,R][L,R] 的和即为 res=sum[R]sum[L1]res=sum[R]-sum[L-1]

    int get(int L, int R)
    {
        return sum[R] - sum[L - 1];
    }
    

    1.2 51nod 1081 子段求和

    题目链接:点击这里

    题意:给出一个长度为 NN 的数组,进行 QQ 次查询,查询从第 ii 个元素开始长度为 ll 的子段所有元素之和。例如,1 3 7 9 11\ 3\ 7\ 9\ -1,查询第 22 个元素开始长度为 33 的子段和,3 + 7 + 9 = 19,输出 19。

    AC代码:

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    typedef long long ll;
    const int N = 50010;
    
    ll sum[N];
    
    int main()
    {
    	int n;
    	cin >> n;
    	
    	for(int i = 1; i <= n; i++)
    	{
    	    int x;
    	    cin >> x;
    	    sum[i] = sum[i - 1] + x;
    	}
    	
    	int T;
    	cin >> T;
    	while(T--)
    	{
    		int l, len;
    		cin >> l >> len;
    		cout << sum[l + len - 1] - sum[l - 1] << endl;
    	}
    	
    	return 0;
    }
    

    2. 二维前缀和

    2.1 原理

    问题描述:假设有一个 nmn*m 大小的矩阵 AA,再给出 qq 次询问,每次询问给出 x1, y1, x2, y2x_1,\ y_1,\ x_2,\ y_2 四个数,要求输出以 (x1,y1)(x_1, y_1) 为左上角坐标和以 (x2,y2)(x_2, y_2) 为右下角坐标的子矩阵的所有元素和。

    如果对于每次询问都进行暴力查询,那么时间复杂度极大,一定会 TLE,此时可以利用二维前缀和来求解。

    以下图中的 a[3][3]=13a[3][3]=13 为例,a[3][3]a[3][3] 的前缀和是以黑框框起来的子矩阵元素之和,即以 (3,3)(3,3) 为右下角、(1,1)(1,1) 为左上角的矩阵中的元素和。

    从递推的角度来看,sum[3][3]=sum[3][2]+sum[2][3]sum[2][2]+a[3][3]sum[3][3]=sum[3][2]+sum[2][3]-sum[2][2]+a[3][3]

    故有:sum[i][j]=sum[i][j1]+sum[i1][j]sum[i1][j1]+a[i][j]sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]

    // 预处理,求以(i,j)为右下角、(1,1)为左上角的矩阵中的元素和
    int init() 
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
    }
    

    那么,每次要查询的答案就是下图中的黄色部分,当给出 x1, y1, x2, y2x_1,\ y_1,\ x_2,\ y_2 时,要查询的值即为 res=sum[x2][y2]sum[x11][y2]sum[x2][y11]+sum[x11][y11]res=sum[x_2][y_2]-sum[x_1-1][y_2]-sum[x_2][y_1-1]+sum[x_1-1][y_1-1]

    int get(int x1, int y1, int x2, int y2) 
    {
        return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
    }
    

    2.2 HDU 1559 最大子矩阵

    题目链接:点击这里

    题意:给你一个 m×nm×n 的整数矩阵,在上面找一个 x×yx×y 的子矩阵,使子矩阵中所有元素的和最大。

    AC代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    const int N = 1010;
    
    int sum[N][N];
    
    int main()
    {
    	int T;
    	cin >> T;
    	while(T--)
    	{
    		memset(sum, 0, sizeof sum);
    		
    		int m, n;       // m行n列
    		cin >> m >> n;
    		
    		int x, y;
    		cin >> x >> y;
    		
    		for(int i = 1; i <= m; i++)
    		{
    			for(int j = 1; j <= n; j++)
    			{
    			    int t;
    				cin >> t;
    				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + t;
    			}
    		}
    		
    		int ans = -1e9;
    		for(int i = 1; i + x - 1 <= m; i++)
    		{
    		    for(int j = 1; j + y - 1 <= n; j++)
    			{
    			    int ii = i + x - 1, jj = j + y - 1;
    				int t = sum[ii][jj] - sum[i - 1][jj] - sum[ii][j - 1] + sum[i - 1][j - 1];
    				ans = max(ans, t);
    			}
    		}
    		
    		cout << ans << endl;
    	}
    	
    	return 0;
    }
    

    3. 一维差分

    3.1 原理

    定义:假设有原数组 a[ ]={a1,a2,a3,...an}a[\ ] = \left\{a_1, a_2, a_3, ... a_n\right\},现构造出一个数组 b[ ]={b1,b2,b3,...bn}b[\ ] = \left\{b_1, b_2, b_3, ... b_n\right\},使得 ai=b1+b2+...bia_i=b_1+b_2+...b_i,那么 b[ ]b[\ ] 就称为 a[ ]a[\ ] 的差分,a[ ]a[\ ] 就称为 b[ ]b[\ ] 的前缀和。可以发现,差分与前缀和是逆运算。

    一维差分可以快速地实现如下两个操作:

    1.区间修改,时间复杂度为 O(1)O(1)

    假如现在要将原数列 a[ ]a[\ ] 区间 [L,R][L,R] 上的每个数都加上 xx,那么通过上述定义可以知道:

    • 第一个受影响的差分数组中的元素为 b[L]b[L],所以令 b[L]+=xb[L]+=x,那么后面数列元素在计算过程中都会加上 xx
    • 最后一个受影响的差分数组中的元素为 b[R]b[R],所以令 b[R+1]=xb[R+1]−=x,那么可以保证不会影响到 RR 之后数列元素的计算。

    这样一来,就不必对区间内每一个数进行处理,只需处理两个端点即可。

    void add(int L, int R, int x)
    {
        b[L] += x;
        b[R + 1] -= x;
    }
    

    2.查询单点,时间复杂度为 O(n)O(n)

    根据上述定义,差分数组 b[i]b[i] 的前缀和就是原序列 a[i]a[i] 的值。

    void get()
    {
        for(int i = 1; i <= n; i++)
    		sum[i] = sum[i - 1] + b[i];
    }
    

    初始化:不需要过分关注差分数组 b[ ]b[\ ] 是怎么构造出来的,只需要知道差分与前缀和是互逆运算即可。事实上,根本就不需要去构造差分数组 b[ ]b[\ ]

    一开始可以把原数组 a[ ]a[\ ] 想象成全是 00,即 a[ ]={0,0,0,...0}a[\ ] = \left\{0, 0, 0, ... 0\right\},此时相应的差分数组 b[ ]b[\ ] 也全是 00, 即 b[ ]={0,0,0,...0}b[\ ] = \left\{0, 0, 0, ... 0\right\},接下来,对原数组 a[ ]a[\ ] 的初始值可以作如下考虑:

    • a[1]a[1] 相当于区间 [1,1][1,1] 的每个数都加上 a[1]a[1]

    • a[2]a[2] 相当于区间 [2,2][2,2] 的每个数都加上 a[2]a[2]

    • a[n]a[n] 相当于区间 [n,n][n,n] 的每个数都加上 a[n]a[n]

    这样,用上面的区间修改操作 add()add() 即可完成赋初始值。

    3.2 牛客小白月赛5 区间 (interval)

    题目链接:点击这里

    题意:Apojacsleam喜欢数组。他现在有一个 nn 个元素的数组 aa,而他要对 a[L]a[R]a[L] \sim a[R] 进行 MM 次操作:

    操作一:将 a[L]a[R]a[L] \sim a[R] 内的元素都加上 PP

    操作二:将 a[L]a[R]a[L] \sim a[R] 内的元素都减去 PP

    最后询问 a[l]a[r]a[l] \sim a[r] 内的元素之和。

    AC代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    typedef long long ll;
    const int N = 1000010;
    
    ll b[N], s[N];
    
    void add(int l, int r, int x)
    {
        b[l] += x;
        b[r + 1] -= x;
    }
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
        
        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            add(i, i, x);
        }
        
        while(m--)
        {
            int op, l, r, p;
            scanf("%d%d%d%d", &op, &l, &r, &p);
            if(op == 1) add(l, r, -p);
            else    add(l, r, p);
        }
        
        // 求差分数组b[]的前缀和(即原数组的值)
        for(int i = 1; i <= n; i++) s[i] = s[i - 1] + b[i];
        
        int l, r;
        scanf("%d%d", &l, &r);
        
        ll ans = 0;
        for(int i = l; i <= r; i++) ans += s[i];
        
        printf("%lld\n", ans);
        
    	return 0;
    }
    

    4. 二维差分

    4.1 原理

    定义:假设有原数组 a[ ][ ]a[\ ][\ ],现构造出一个数组 b[ ][ ]b[\ ][\ ],使得 a[i][j]a[i][j] 等于 b[i][j]b[i][j] 格子左上部分所有元素的和,那么 b[ ][ ]b[\ ][\ ] 就称为 a[ ][ ]a[\ ][\ ] 的差分,a[ ][ ]a[\ ][\ ] 就称为 b[ ][ ]b[\ ][\ ] 的前缀和。可以发现,差分与前缀和是逆运算。

    类比于一维差分,二维差分同样可以快速地实现如下两个操作:

    1.将原数组 a[ ][ ]a[\ ][\ ] 的以 (x1,y1)(x_1, y_1) 为左上角、(x2,y2)(x_2, y_2) 为右下角的矩形区域里的每个数都加上 cc

    // 给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c
    void add(int x1, int y1, int x2, int y2, int c)
    {
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }
    

    2.查询单点,差分数组 b[i][j]b[i][j] 的前缀和就是原数组 a[i][j]a[i][j] 的值。

    // 求以(i,j)为右下角、(1,1)为左上角的矩阵中的元素和
    void get()
    {
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= m; j++)
    			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + b[i][j];
    }
    

    同理,不需要过分关注二维差分数组 b[ ][ ]b[\ ][\ ] 是如何构造出来的,仅仅依靠上面的 add()add() 操作即可完成赋初值。

    4.2 HDU 6514 Monitor

    题目链接:点击这里

    题意:Xiaoteng 有一个 n×mn × m 的矩形庄稼地,为了抓到小偷,安装了 pp 个监控,每个监控都有一个矩形的监视范围,左上角为 (x1,y1)(x_1, y_1),右下角为 (x2,y2)(x_2, y_2)。小偷们会来偷 qq 次,每次小偷们的作案地点都是一个矩形区域,左上角为 (x1,y1)(x_1, y_1),右下角为 (x2,y2)(x_2, y_2)。问每次小偷们作案时,能否看到全部的小偷。

    思路:将每个监控的矩形监视区域里的每个数都加上 11,都操作在差分数组上。求差分数组的前缀和得到原数组,如果原数组中的值大于 11,说明该点被多个监控覆盖,我们只需要记 11 个即可。对于小偷们每次作案的矩形区域,看是否充满了 11,如果全是 11(即作案的矩形与原数组的矩形值相等),则输出 YES;否则,输出NO。

    AC代码:

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    typedef long long ll;
    
    int main()
    {
        int n, m;
        while(~scanf("%d%d", &n, &m))
        {
            vector<vector<int>> f(n + 10, vector<int>(m + 10, 0));
            
            int p;
            scanf("%d", &p);
            while(p--)
            {
                // 给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上1
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                f[x1][y1]++;
                f[x2 + 1][y1]--;
                f[x1][y2 + 1]--;
                f[x2 + 1][y2 + 1]++;
            }
            
            // 求差分数组的前缀和,得到原数组的值
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            
            // 如果被监控覆盖了多次,则只记一次
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    if(f[i][j] > 1)
                        f[i][j] = 1;
            
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            
            int q;
            scanf("%d", &q);
            while(q--)
            {
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                
                int t1 = (x2 - x1 + 1) * (y2 - y1 + 1);
                int t2 = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
                
                if(t1 == t2)    puts("YES");
                else    puts("NO");
            }
        }
        
        return 0;
    }
    
    展开全文
  • 前缀、中缀、后缀表达式

    万次阅读 多人点赞 2011-09-09 14:54:38
    关键字:概念, 前缀表达式, 前缀记法, 中缀表达式, 中缀记法, 波兰式, 后缀表达式, 后缀记法, 逆波兰式 它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与...

    关键字:概念, 前缀表达式, 前缀记法, 中缀表达式, 中缀记法, 波兰式, 后缀表达式, 后缀记法, 逆波兰式


    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。

    举例:
    (3 + 4) × 5 - 6 就是中缀表达式
    - × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

    中缀表达式(中缀记法)
    中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
    虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

    前缀表达式(前缀记法、波兰式)
    前缀表达式的运算符位于操作数之前。

    前缀表达式的计算机求值:
    从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
    例如前缀表达式“- × + 3 4 5 6”:
    (1) 从右至左扫描,将6、5、4、3压入堆栈;
    (2) 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈;
    (3) 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈;
    (4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。
    可以看出,用计算机计算前缀表达式的值是很容易的。

    将中缀表达式转换为前缀表达式:
    遵循以下步骤:
    (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    (2) 从右至左扫描中缀表达式;
    (3) 遇到操作数时,将其压入S2;
    (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
    (4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1;
    (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
    (5) 遇到括号时:
    (5-1) 如果是右括号“)”,则直接压入S1;
    (5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃;
    (6) 重复步骤(2)至(5),直到表达式的最左边;
    (7) 将S1中剩余的运算符依次弹出并压入S2;
    (8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
    例如,将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下:
    扫描到的元素 S2(栈底->栈顶) S1 (栈底->栈顶) 说明
    5 5 数字,直接入栈
    - 5 - S1为空,运算符直接入栈
    ) 5 - ) 右括号直接入栈
    4 5 4 - ) 数字直接入栈
    × 5 4 - ) × S1栈顶是右括号,直接入栈
    ) 5 4 - ) × ) 右括号直接入栈
    3 5 4 3 - ) × ) 数字
    + 5 4 3 - ) × ) + S1栈顶是右括号,直接入栈
    2 5 4 3 2 - ) × ) + 数字
    ( 5 4 3 2 + - ) × 左括号,弹出运算符直至遇到右括号
    ( 5 4 3 2 + × - 同上
    + 5 4 3 2 + × - + 优先级与-相同,入栈
    1 5 4 3 2 + × 1 - + 数字
    到达最左端 5 4 3 2 + × 1 + - S1中剩余的运算符
    因此结果为“- + 1 × + 2 3 4 5”。

    后缀表达式(后缀记法、逆波兰式)
    后缀表达式与前缀表达式类似,只是运算符位于操作数之后。

    后缀表达式的计算机求值:
    与前缀表达式类似,只是顺序是从左至右:
    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
    例如后缀表达式“3 4 + 5 × 6 -”:
    (1) 从左至右扫描,将3和4压入堆栈;
    (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
    (3) 将5入栈;
    (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
    (5) 将6入栈;
    (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

    将中缀表达式转换为后缀表达式:
    与转换为前缀表达式相似,遵循以下步骤:
    (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    (2) 从左至右扫描中缀表达式;
    (3) 遇到操作数时,将其压入S2;
    (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
    (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
    (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
    (5) 遇到括号时:
    (5-1) 如果是左括号“(”,则直接压入S1;
    (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
    (6) 重复步骤(2)至(5),直到表达式的最右边;
    (7) 将S1中剩余的运算符依次弹出并压入S2;
    (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

    例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下:
    扫描到的元素 S2(栈底->栈顶) S1 (栈底->栈顶) 说明
    1 1 数字,直接入栈
    + 1 + S1为空,运算符直接入栈
    ( 1 + ( 左括号,直接入栈
    ( 1 + ( ( 同上
    2 1 2 + ( ( 数字
    + 1 2 + ( ( + S1栈顶为左括号,运算符直接入栈
    3 1 2 3 + ( ( + 数字
    ) 1 2 3 + + ( 右括号,弹出运算符直至遇到左括号
    × 1 2 3 + + ( × S1栈顶为左括号,运算符直接入栈
    4 1 2 3 + 4 + ( × 数字
    ) 1 2 3 + 4 × + 右括号,弹出运算符直至遇到左括号
    - 1 2 3 + 4 × + - -与+优先级相同,因此弹出+,再压入-
    5 1 2 3 + 4 × + 5 - 数字
    到达最右端 1 2 3 + 4 × + 5 - S1中剩余的运算符

    因此结果为“1 2 3 + 4 × + 5 -”(注意需要逆序输出)。

    编写Java程序将一个中缀表达式转换为前缀表达式和后缀表达式,并计算表达式的值。其中的toPolishNotation()方法将中缀表达式转换为前缀表达式(波兰式)、toReversePolishNotation()方法则用于将中缀表达式转换为后缀表达式(逆波兰式):

    注:
    (1) 程序很长且注释比较少,但如果将上面的理论内容弄懂之后再将程序编译并运行起来,还是比较容易理解的。有耐心的话可以研究一下。(2) 此程序是笔者为了说明上述概念而编写,仅做了简单的测试,不保证其中没有Bug,因此不要将其用于除研究之外的其他场合。


    package qmk.simple_test;
    import java.util.Scanner;
    import java.util.Stack;
    /**
     * Example of converting an infix-expression to
     * Polish Notation (PN) or Reverse Polish Notation (RPN).
     * Written in 2011-8-25
     * @author QiaoMingkui
     */
    public class Calculator {
          public static final String USAGE = "== usage ==\n"
                + "input the expressions, and then the program "
                + "will calculate them and show the result.\n"
                + "input 'bye' to exit.\n";
          /**
           * @param args
           */
          public static void main(String[] args) {
                System.out.println(USAGE);
                Scanner scanner = new Scanner(System.in);
                String input = "";
                final String CLOSE_MARK = "bye";
                System.out.println("input an expression:");
                input = scanner.nextLine();
                while (input.length() != 0
                      && !CLOSE_MARK.equals((input))) {
                      System.out.print("Polish Notation (PN):");
                      try {
                            toPolishNotation(input);
                      } catch (NumberFormatException e) {
                            System.out.println("\ninput error, not a number.");
                      } catch (IllegalArgumentException e) {
                            System.out.println("\ninput error:" + e.getMessage());
                      } catch (Exception e) {
                            System.out.println("\ninput error, invalid expression.");
                      }
                      System.out.print("Reverse Polish Notation (RPN):");
                      try {
                            toReversePolishNotation(input);
                      } catch (NumberFormatException e) {
                            System.out.println("\ninput error, not a number.");
                      } catch (IllegalArgumentException e) {
                            System.out.println("\ninput error:" + e.getMessage());
                      } catch (Exception e) {
                            System.out.println("\ninput error, invalid expression.");
                      }
                      System.out.println("input a new expression:");
                      input = scanner.nextLine();
                }
                System.out.println("program exits");
          }
          /**
           * parse the expression , and calculate it.
           * @param input
           * @throws IllegalArgumentException
           * @throws NumberFormatException
           */
          private static void toPolishNotation(String input)
                      throws IllegalArgumentException, NumberFormatException {
                int len = input.length();
                char c, tempChar;
                Stack<Character> s1 = new Stack<Character>();
                Stack<Double> s2 = new Stack<Double>();
                Stack<Object> expression = new Stack<Object>();
                double number;
                int lastIndex = -1;
                for (int i=len-1; i>=0; --i) {
                      c = input.charAt(i);
                      if (Character.isDigit(c)) {
                            lastIndex = readDoubleReverse(input, i);
                            number = Double.parseDouble(input.substring(lastIndex, i+1));
                            s2.push(number);
                            i = lastIndex;
                            if ((int) number == number)
                                  expression.push((int) number);
                            else
                                  expression.push(number);
                      } else if (isOperator(c)) {
                            while (!s1.isEmpty()
                                        && s1.peek() != ')'
                                        && priorityCompare(c, s1.peek()) < 0) {
                                  expression.push(s1.peek());
                                  s2.push(calc(s2.pop(), s2.pop(), s1.pop()));
                            }
                            s1.push(c);
                      } else if (c == ')') {
                            s1.push(c);
                      } else if (c == '(') {
                            while ((tempChar=s1.pop()) != ')') {
                                  expression.push(tempChar);
                                  s2.push(calc(s2.pop(), s2.pop(), tempChar));
                                  if (s1.isEmpty()) {
                                        throw new IllegalArgumentException(
                                              "bracket dosen't match, missing right bracket ')'.");
                                  }
                            }
                      } else if (c == ' ') {
                            // ignore
                      } else {
                            throw new IllegalArgumentException(
                                        "wrong character '" + c + "'");
                      }
                }
                while (!s1.isEmpty()) {
                      tempChar = s1.pop();
                      expression.push(tempChar);
                      s2.push(calc(s2.pop(), s2.pop(), tempChar));
                }
                while (!expression.isEmpty()) {
                      System.out.print(expression.pop() + " ");
                }
                double result = s2.pop();
                if (!s2.isEmpty())
                      throw new IllegalArgumentException("input is a wrong expression.");
                System.out.println();
                if ((int) result == result)
                      System.out.println("the result is " + (int) result);
                else
                      System.out.println("the result is " + result);
          }
          /**
           * parse the expression, and calculate it.
           * @param input
           * @throws IllegalArgumentException
           * @throws NumberFormatException
           */
          private static void toReversePolishNotation(String input)
                      throws IllegalArgumentException, NumberFormatException {
                int len = input.length();
                char c, tempChar;
                Stack<Character> s1 = new Stack<Character>();
                Stack<Double> s2 = new Stack<Double>();
                double number;
                int lastIndex = -1;
                for (int i=0; i<len; ++i) {
                      c = input.charAt(i);
                      if (Character.isDigit(c) || c == '.') {
                            lastIndex = readDouble(input, i);
                            number = Double.parseDouble(input.substring(i, lastIndex));
                            s2.push(number);
                            i = lastIndex - 1;
                            if ((int) number == number)
                                  System.out.print((int) number + " ");
                            else
                                  System.out.print(number + " ");
                      } else if (isOperator(c)) {
                            while (!s1.isEmpty()
                                        && s1.peek() != '('
                                        && priorityCompare(c, s1.peek()) <= 0) {
                                  System.out.print(s1.peek() + " ");
                                  double num1 = s2.pop();
                                  double num2 = s2.pop();
                                  s2.push(calc(num2, num1, s1.pop()));
                            }
                            s1.push(c);
                      } else if (c == '(') {
                            s1.push(c);
                      } else if (c == ')') {
                            while ((tempChar=s1.pop()) != '(') {
                                  System.out.print(tempChar + " ");
                                  double num1 = s2.pop();
                                  double num2 = s2.pop();
                                  s2.push(calc(num2, num1, tempChar));
                                  if (s1.isEmpty()) {
                                        throw new IllegalArgumentException(
                                              "bracket dosen't match, missing left bracket '('.");
                                  }
                            }
                      } else if (c == ' ') {
                            // ignore
                      } else {
                            throw new IllegalArgumentException(
                                        "wrong character '" + c + "'");
                      }
                }
                while (!s1.isEmpty()) {
                      tempChar = s1.pop();
                      System.out.print(tempChar + " ");
                      double num1 = s2.pop();
                      double num2 = s2.pop();
                      s2.push(calc(num2, num1, tempChar));
                }
                double result = s2.pop();
                if (!s2.isEmpty())
                      throw new IllegalArgumentException("input is a wrong expression.");
                System.out.println();
                if ((int) result == result)
                      System.out.println("the result is " + (int) result);
                else
                      System.out.println("the result is " + result);
          }
          /**
           * calculate the two number with the operation.
           * @param num1
           * @param num2
           * @param op
           * @return
           * @throws IllegalArgumentException
           */
          private static double calc(double num1, double num2, char op)
                      throws IllegalArgumentException {
                switch (op) {
                case '+':
                      return num1 + num2;
                case '-':
                      return num1 - num2;
                case '*':
                      return num1 * num2;
                case '/':
                      if (num2 == 0) throw new IllegalArgumentException("divisor can't be 0.");
                      return num1 / num2;
                default:
                      return 0; // will never catch up here
                }
          }
          /**
           * compare the two operations' priority.
           * @param c
           * @param peek
           * @return
           */
          private static int priorityCompare(char op1, char op2) {
                switch (op1) {
                case '+': case '-':
                      return (op2 == '*' || op2 == '/' ? -1 : 0);
                case '*': case '/':
                      return (op2 == '+' || op2 == '-' ? 1 : 0);
                }
                return 1;
          }
          /**
           * read the next number (reverse)
           * @param input
           * @param start
           * @return
           * @throws IllegalArgumentException
           */
          private static int readDoubleReverse(String input, int start)
                      throws IllegalArgumentException {
                int dotIndex = -1;
                char c;
                for (int i=start; i>=0; --i) {
                      c = input.charAt(i);
                      if (c == '.') {
                            if (dotIndex != -1)
                                  throw new IllegalArgumentException(
                                        "there have more than 1 dots in the number.");
                            else
                                  dotIndex = i;
                      } else if (!Character.isDigit(c)) {
                            return i + 1;
                      } else if (i == 0) {
                            return 0;
                      }
                }
                throw new IllegalArgumentException("not a number.");
          }
          
          /**
           * read the next number
           * @param input
           * @param start
           * @return
           * @throws IllegalArgumentException
           */
          private static int readDouble(String input, int start)
          throws IllegalArgumentException {
                int len = input.length();
                int dotIndex = -1;
                char c;
                for (int i=start; i<len; ++i) {
                      c = input.charAt(i);
                      if (c == '.') {
                            if (dotIndex != -1)
                                  throw new IllegalArgumentException(
                                  "there have more than 1 dots in the number.");
                            else if (i == len - 1)
                                  throw new IllegalArgumentException(
                                  "not a number, dot can't be the last part of a number.");
                            else
                                  dotIndex = i;
                      } else if (!Character.isDigit(c)) {
                            if (dotIndex == -1 || i - dotIndex > 1)
                                  return i;
                            else
                                  throw new IllegalArgumentException(
                                  "not a number, dot can't be the last part of a number.");
                      } else if (i == len - 1) {
                            return len;
                      }
                }
                
                throw new IllegalArgumentException("not a number.");
          }
          /**
           * return true if the character is an operator.
           * @param c
           * @return
           */
          private static boolean isOperator(char c) {
                return (c=='+' || c=='-' || c=='*' || c=='/');
          }
    }


    下面是程序运行结果(绿色为用户输入):

    == usage ==
    input the expressions, and then the program will calculate them and show the result.
    input 'bye' to exit.

    input an expression:
    3.8+5.3
    Polish Notation (PN):+ 3.8 5.3
    the result is 9.1
    Reverse Polish Notation (RPN):3.8 5.3 +
    the result is 9.1
    input a new expression:
    5*(9.1+3.2)/(1-5+4.88)
    Polish Notation (PN):/ * 5 + 9.1 3.2 + - 1 5 4.88
    the result is 69.88636363636364
    Reverse Polish Notation (RPN):5 9.1 3.2 + * 1 5 - 4.88 + /
    the result is 69.88636363636364
    input a new expression:
    1+((2+3)*4)-5
    Polish Notation (PN):- + 1 * + 2 3 4 5
    the result is 16
    Reverse Polish Notation (RPN):1 2 3 + 4 * + 5 -
    the result is 16
    input a new expression:
    bye
    program exits


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

    万次阅读 多人点赞 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;
    }

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

    展开全文
  • 前缀

    万次阅读 多人点赞 2019-02-07 10:59:08
    对于一个给定的数列 A, 它的前缀和数列S 是通过递推能求出来得 部分和,即数列A中某个下标区间内的数的和,可以表示为前缀和相减的形式: 代码: for(int i = 1...

    对于一个给定的数列 A, 它的前缀和数列S 是通过递推能求出来得

                                                       S[i] = \sum_{j=1}^{i} A[j]

    部分和,即数列A中某个下标区间内的数的和,可以表示为前缀和相减的形式:

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

    代码: 

        for(int i = 1 ; i<=n ; i++ )
    	cin >>A[i] ;
    	
    	for(int i = 1 ; i<=n ; i++ )
    	s[i] = s[i-1] + A[i] ;
    	

    所以每次我们询问区间[L,R] 的和,只需要计算s[R] - s[L-1] 就可以了. 

    [差分]  

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

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

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

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

    当然最暴力的手段是对于每一次操作,我们都要去遍历一下数组再求前缀和,但这样会超时 , 我们用差分就比较方便了. 

    我们先来直观的认识一下差分数组:

    1 [定义]:

    对于已知有n个元素的数列A[1~n],我们可以建立记录它每项与前一项的差值的差分数组B:显然:B[1]=A[1]-0;对于整数i∈[2,n],取A[i]-A[i-1]为其差分数组B[i]的值

    2 [简单性质]

    (1)计算数列各项的值:可以发现数列A的第i项的值是可以用其差分数组B的前n项和计算,即A[i]=∑B[j](1<=j<=i)

    (2)计算数列的前缀和:第i项的前缀和即为数列前i项的和,那么推导可知

    即可用差分数组求出数列前缀和

    3[用途]:

              (1)  快速处理区间加减操作:

                 如果进行区间加减操作,且修改的区间连续,那么若将[x,y]区间内A[i]各加val,我们就可以只对其差分数组B的x和y这两               项进行修改,x项B[x]加val ,y项 B[y+1]减val。

              (2)  询问区间和问题:

                 在保证(1)正确修改的基础上,我们可以由性质(2)计算出数列各项的前缀和数组sum各项的值;那么显然,区间                   [L,R]的和即A[L]+…+A[R] = ans = sum[R]-sum[L-1].

          

    #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;
    }
    

    设a数组表示原始的数组;

    设d[i]=a[i]-a[i-1](1<i≤n,d[1]=a[1]);

    设f[i]=f[i-1]+d[i](1<i≤n,f[1]=d[1]=a[1]);

    设sum[i]=sum[i-1]+f[i](1<i≤n,sum[1]=f[1]=d[1]=a[1])。

     

    举个例子,我们求1~3的区间和.

    后面的可以依次类推。

    那么,对于一个操作,我们可以让d[x]加上z,让d[y+1]减小z,就可以了。

    还用刚才的例子。

    后面的可以依次类推。

    参考https://blog.csdn.net/zsyz_ZZY/article/details/79918809

    #include<cstdio>
    	int n,m,q;
    	int a[100000],d[100000],f[100000],sum[100000];
    int main()
    {
    	int x,y,z;
    	scanf("%d %d %d",&n,&m,&q);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    		d[i]=a[i]-a[i-1];
    	}
    	for(int i=1;i<=m;i++)
    	{
    		scanf("%d %d %d",&x,&y,&z);
    		d[x]+=z;
    		d[y+1]-=z;
    	}		
    	for(int i=1;i<=n;i++)
    	{
    		f[i]=f[i-1]+d[i];
    		sum[i]=sum[i-1]+f[i];
    	}
    	for(int i=1;i<=q;i++)
    	{
    		scanf("%d %d",&x,&y);
    		printf("%d\n",sum[y]-sum[x-1]);
    	}
    }
    

    对于二维数组前缀和.

    \large S[i,j] = \sum_{x=1}^{i} \sum_{y=1}^{j} A[x,y]

    如图,我们观察 S[i,j] ,S[i-1,j] , S[i,j-1] , S[i-1,j-1] ; 

    s[i,j]
    S[ i , j ]
    S[ i-1 , j ]

     

    S[ i -1 , j ] +S[i , j -1 ] 
     S[ i , j-1 ] 

     

     

     


     

     

    S[ i-1,  j ] +S[i , j-1 ] - S[ i- 1 ,j -1 ] 

     

     

     

     

     

     

    容易得到,  S[ i , j ] = S[ i- 1 ,j ] + S[i , j-1 ]  - S[i - 1 , j-1 ] + A[ i , j ]    , 式子中就包含容斥原理 .

     

    为方便理解贴个图

    假如我想求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;
    }
    

    参考博客:  https://blog.csdn.net/k_r_forever/article/details/81775899

    展开全文
  • 英语前缀总结

    万次阅读 2017-07-27 19:46:26
    常见的前缀 1. 表示否定意义的前缀 1) 纯否定前缀 a- ,an- , asymmetry (不对称) anhydrous (无水的) Dis- dishonest,dislike In-,ig-,il,im,ir,incapable,inability,ignoble,impossible,immoral...
  • 什么是前缀和 前缀和(Prefix Sum)的定义为:对于一个给定的数列 A, 它的前缀和数列 S 是通过递推能求出来得 部分和。 例如: C++实现 //假设数组a和前缀和数组s都已经定义 int i; //初始条件 a[0] = 0; s[0...
  • 前缀和并行算法

    千次阅读 2013-03-03 16:55:56
    多核中的并行前缀和计算 前缀和计算在并行计算中很有用,因为在处理负载平衡问题时,经常需要将若干段数据重新平分,计算前缀和通常是一种有效的将数据平分的方法。例如在并行基数排序中,就会用到了前缀和的计算。...
  • 前缀和——(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-05-02 17:32:06
    最近做题用到了这个,自己学习了一下,然后...1.一维前缀和 这个主要是应用于在O(1)时间内求一个序列和。如给一个序列s,求s[i]+s[i+1]+s[i+2]+...s[n]。 算法十分简单,用数组sum[i]记录前n项序列s[i]的和(su...
  • 二维前缀和详解

    千次阅读 多人点赞 2018-09-22 16:46:59
    这几天在打比赛时遇到了二维前缀和,看了一下深有体会,发一篇详解。 首先,什么是前缀和?一个数列,我们要计算某个区间内的和,该怎么做呢?正所谓暴力出奇迹,这一个也可以,我们暴力枚举每一个区间内的数并且...
  • 前缀和算法

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

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

    千次阅读 2017-05-09 12:47:38
    前缀和作为一个可以维护区间信息且易于实现的数据结构,深受算法竞赛青睐,我曾在多场比赛中遇到过前缀和的问题,因此我觉得有必要好好地整理一下关于前缀和的知识点。一方面利于自己查漏补缺,另一方面也为更多喜欢...
  • 高维前缀和总结

    2019-10-09 00:29:31
    高维前缀和一般解决这类问题: 对于所有的\(i,0\leq i\leq 2^n-1\),求解\(\sum_{j\subset i}a_j\)。 显然,这类问题可以直接枚举子集求解,但复杂度为\(O(3^n)\)。如果我们施展高维前缀和的话,复杂度可以到\(O(n...
  • 高维前缀和

    千次阅读 2017-08-10 20:24:26
    前几天补2016大连icpc现场赛的题目时,遇到了一个树分治,这个题除了套一个树分治的模板还要加上高维前缀和的东西。然后发现自己什么都不会….(只是一个铜牌题),补了一下相关的知识,先写一下高维前缀和吧。for(int...
  • 矩阵前缀和

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

    千次阅读 2018-11-28 21:33:37
    前缀和后缀是什么呢? 举个例子: +34 3+4 34+ 前缀 中缀 后缀 也称为: 波兰式 逆波兰式 --------------------- 那就以 X=A+B*(C-D)/E 为例: 先转换成前缀表达式 第一步:先加括号:(X=(A + ( ( ...
  • 前缀和 什么是前缀和   前缀和顾名思义就是指一个数组的某一个下标的(包括该下标)之前的所有数组元素的和。现在我们假设有某一数组a = [1, 2, 3, 4, 5, 6, 7, 8, 9]。其前缀和数组为sum,那么sum数组与a数组对应...

空空如也

1 2 3 4 5 ... 20
收藏数 706,660
精华内容 282,664
关键字:

前缀