前缀和

Author Avatar
Axell 8月 14, 2018
  • 在其它设备中阅读本文章

前缀和:

每一个数分别储存它的前面所有的数字之和,用于优化运算速度

注意:前缀和数组的数据范围要足够大

eg:

题目描述

有N条线段,已知每条线段的起点和终点(0500000内的整数),然后有M个询问,每次询问一个点(0500000内的整数),求这个点在多少条线段上出现过?

输入
第一行N线段条数
接下来N行,每行两个数(l,r),线段的起点和终点
第N+2行一个数M询问个数
接下来M行,每行一个点
输出
对于每个询问,求答案
常规会采用for循环,将l,r之间的数在数组上+1,但会超时
本题采用:
var
    i,j,n,m,l,r:longint;
    a,b:array[0..500000] of longint;
begin
    readln(n);
    for i:=1 to n do 
     begin
        readln(l,r);
        a[l]:=a[l]+1;
        a[r+1]:=a[r+1]-1; //+1表示线段起点,-1表示线段终点
     end;
    b[0]:=a[0]; //可能0是某条线段的起点
    for i:=1 to 500000 do 
      b[i]:=b[i-1]+a[i]; //如果不是起点或终点,则线段数与前一个点相同,起点则+1,终点则-1
    readln(m);
    for i:=1 to m do
     begin
        readln(j);
        writeln(b[j]); //输出结果
     end;
end.

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/25/