前缀和：

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

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

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://hs-blog.axell.top/archives/25/