中二羊专题:栋栋的入门题(前缀和)

30
四月
2021

原题

标题虽然是栋栋的入门题,但它并不是入门题。
原题的题目描述是:

给出N个整数,以及M个求和范围,求出每一个范围的数字的和。

提示:显然,这并不是一道入门题。

这就要用到一种新的思想:前缀思想。

进入正题

数组 a a a (此处方便讲解,忽略下标 0 0 0 )有这 5 5 5 个数字: 1 , 3 , 2 , 1 , 5 1,3,2,1,5 1,3,2,1,5 。你求 a 1 + . . . + a 3 a_1+...+a_3 a1+...+a3 是以下代码:

for(int i=1;i<=3;i++)ans+=a[i];

再假设数组 b b b m m m 个数字。你需要求 b x + . . . + b y b_x+...+b_y bx+...+by 。一般人用以下代码:

for(int i=x;i<=y;i++)ans+=b[i];

你有 n n n 次访问(即求 n n n 次从 b x + . . . + b y b_x+...+b_y bx+...+by )。那么你代码应该会是这样:

for(int i=1;i<=n;i++){
	cin>>x>>y;
	for(int j=x;j<=y;j++)ans+=b[j];
}

但这样子太慢了。
但是我们还有一种方法解决。
我们可以令 c i c_i ci b 1 + b 2 + . . . + b i b_1+b_2+...+b_i b1+b2+...+bi 。那么求 b x + . . . + b y b_x+...+b_y bx+...+by 就非常快了。 c y − c x − 1 c_y-c_{x-1} cycx1

解释

已知 c y = b 1 + . . . + b y c_y=b_1+...+b_y cy=b1+...+by c x = b 1 + . . . + b x c_x=b_1+...+b_x cx=b1+...+bx 。所以说(此处化简):
c y − c x − 1 = b 1 + . . . + b y − ( b 1 + . . . + b x − 1 ) = b x + . . . + b y c_y-c_{x-1}=b_1+...+b_y-(b_1+...+b_{x-1})=b_x+...+b_y cycx1=b1+...+by(b1+...+bx1)=bx+...+by

代码

建议别抄。这里只是给一个例子。

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
namespace FastIo{
    typedef unsigned long long ull;
    typedef __uint128_t L;
    static char buf[100000],*p1=buf,*p2=buf;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    class FastMod{
        public:
            FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
            ull reduce(ull a){
                ull q=(ull)((L(m)*a)>>64);
                ull r=a-q*b;
                return r>=b?r-b:r;
            }
        private:
            ull b,m;
    };
    FastMod QM(10);
    class QIO{
    	public:
    		inline void read(int &x){
    			x=0,ch=gc;
    			while(!isdigit(ch))ch=gc;
    			while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
			}
			void write(int a){
				if(a>9)write(a/10);
				putchar(QM.reduce(a)^48);
			}
		private:
			char ch;
	};
	QIO qrw;
}
using namespace FastIo;
int a[1000001];
signed main(){
	register int i(1);
	int n,m,x,y;
	qrw.read(n);
	qrw.read(m);
	for(;i<=n;i=-~i){
		qrw.read(x);
		a[i]=a[i-1]+x;
	}
	for(i=1;i<=m;i=-~i){
		qrw.read(x);
		qrw.read(y);
		qrw.write(a[y]-a[x-1]);
		putchar('\n');
	}
    exit(0);
    return 0;
}
TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员