草庐IT

【前缀和】

Tom·猫 2023-04-08 原文

前缀和

前缀和

输入一个长度为 n的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r

对于每个询问，输出原序列中从第 l 个数到第 r个数的和。

输入格式第一行包含两个整数 n和 m

第二行包含 n个整数，表示整数数列。

接下来 m行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式共 m 行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n ,
1≤n,m≤100000 ,
−1000≤数列中元素的值≤1000

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

前缀和的用处：前缀和数组能以On(1)的方式求出给定范围内数组的和。

在很多地方都用的上前缀和数组，只是它很容易被人忽略，所以得多练练加深印象。

解题思路：本题是一维数组的前缀和，思路很简单，直接在原数组上进行修改即可。

求前缀和数组：设原数组为a[],我们可知递推方程为a[i]=a[i-1]+a[i]

前缀和数组求出后，要知道给定范围内[i,j]的数组和，就很简单了
方程为vla=a[j]-a[i-1]

代码：

#include<iostream>

using namespace std;

const int N=100010;
int a[N];
int b[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    
    for(int i=1;i<=n;i++) a[i]=a[i-1]+a[i];
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        cout<<a[r]-a[l-1]<<endl;
    }
}

子矩阵的和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式
共 q行，每行输出一个询问的结果。

数据范围：

1≤n,m≤1000
,
1≤q≤200000
,
1≤x1≤x2≤n
,
1≤y1≤y2≤m
,
−1000≤矩阵内元素的值≤1000

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

本题大致意思同上题差不多，只是从一维数组变为二维数组，有些不太好理解；

要求给定范围内的数组和 ，先说求二维前缀和的递推公式

a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+a[i][j];

看图：
黑颜色即为所求，但是当我们在减去多余部分的时候，有一块区域会被减去两次，如上图，就是橙色的区域，因此我们需要将其加回来。
代码：

#include<iostream>

using namespace std;

const int N=1010;
int a[N][N];

int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m;j++)
           {
                scanf("%d",&a[i][j]);
           }
       }
         
   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[i][j];
           }
       }
       
        
        while(q--)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int val=a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
            cout<<val<<endl;
        }
        return 0;
}

结语

下篇会描述前缀和的兄弟，差分数组。

如果觉得有帮助的话，记得
一键三连哦ヾ(≧▽≦*)o。

前缀和spanclasstoken算法acwing前缀和

有关【前缀和】的更多相关文章

  1. ruby - 为什么 ruby​​ 中的变量前缀允许在方法调用中省略括号？ - 2

    在DavidFlanagan的TheRubyProgrammingLanguage中；松本幸弘theystatethatthevariableprefixes($,@,@@)areonepricewepayforbeingabletoomitparenthesesaroundmethodinvocations.谁可以给我解释一下这个？ 最佳答案 这是我不成熟的意见。如果我错了，请纠正我。假设实例变量没有@前缀，那么我们如何声明一个实例变量？classMyClassdefinitialize#Herefooisaninstanceva

  2. ruby - Ruby 错误消息中的单字母前缀是什么意思？ - 2

    Ruby错误消息通常包含带单字母前缀的词法常量，例如:syntaxerror,unexpectedtIDENTIFIER,expectingkENDt和k从哪里来？还有其他字母吗？可能的关键字的主列表？ 最佳答案 对于此类问题，parse.y通常是看的地方。如果没记错的话，'t'代表token，而'k'代表关键字。以下是表示标识符的不同标记(在其他事物的名称意义上):%tokentIDENTIFIERtFIDtGVARtIVARtCONSTANTtCVARtLABEL我通过快速搜索找到的kEND的唯一定义是k_end:k_end:k

  3. ruby - 如何为散列中的每个键添加前缀？ - 2

    我的哈希中有以下键:address,postcode我想为它们中的每一个添加“shipping_”前缀，这样它们就变成了:shipping_address,shipping_postcode相反。我该怎么做？ 最佳答案 hsh1={'address'=>"foo",'postcode'=>"bar"}hsh2=Hash[hsh1.map{|k,v|[k.dup.prepend("shipping_"),v]}]phsh2#>>{"shipping_address"=>"foo","shipping_postcode"=>"bar"}

  4. ruby - 获取字符串所有前缀的列表 - 2

    RubyString类中是否有任何内置函数可以为我提供Ruby中字符串的所有前缀。像这样的东西:"ruby".all_prefixes=>["ruby","rub","ru","r"]目前我已经为此做了一个自定义函数:defall_prefixessearch_stringdup_string=search_string.dupreturn_list=[]while(dup_string.length!=0)return_list但我正在寻找更像ruby、更少代码和神奇的东西。注意:当然不用说original_string应该保持原样。 最佳答案

  5. ruby-on-rails - Nokogiri 和 XPath 中未定义的命名空间前缀 - 2

    我正在尝试解析YoutubeGdata以查看是否存在具有给定ID的视频。但是没有普通的标签，而是带有命名空间。在链接上http://gdata.youtube.com/feeds/api/videos?q=KgfdlZuVz7I有标签:1有命名空间openSearch:xmlns:openSearch='http://a9.com/-/spec/opensearchrss/1.0/'但我不知道如何在Nokogiri和Ruby中处理它。部分代码如下:xmlfeed=Nokogiri::HTML(open("http://gdata.youtube.com/feeds/api/videos

  6. ruby-on-rails - 冒号前缀和附加之间的区别(:item vs item:) - 2

    在ruby​​中追加和前置冒号有什么区别？例子:#Inrailsyouoftenhavethingslikethis:has_many:models,dependent::destroy为什么dependent:有一个冒号，而:models和:destroy有一个冒号？有什么区别？ 最佳答案 这是Ruby1.9中的新语法，用于定义散列中作为键的符号。前置和附加的:都定义了一个symbol，但后者仅在散列初始化期间有效。你可以想到一个symbol作为轻量级字符串常量。相当于:dependent=>:destroy在1.9之前，散列是使

  7. ruby - 启动没有前缀 "Ruby"的 Ruby - 2

    我正在使用OSX(使用bash)，并且是unix的新手。我想知道是否可以修改一些文件以便运行ruby​​程序，我不需要“rubyfile.rb”，而是可以运行“ruby.rb”。有理由不这样做吗？谢谢! 最佳答案 是的，你可以做到这一点。假设ruby.rb里面有这样的东西:#!/usr/bin/envrubyputs'Helloworld'在命令行:chmod+xruby​​.rb这使其可执行。然后你可以这样执行:./ruby.rb有关详细信息，请参阅wikibooks.编辑(JörgWMittag):使用#!/usr/bin/en

  8. ruby - Amazon 基于前缀的 S3 策略不起作用(AWS、IAM、STS、Ruby) - 2

    我正在构建一个应用程序，该应用程序使用亚马逊的安全token服务来创建临时用户以访问S3存储桶上的子目录。用户由IAM用户创建，该用户对存储桶具有完全读/写访问权限(以及创建用户所需的权限)。我创建的用户与session过期等完美配合，但我在制定正确的策略以允许基于前缀的key列表方面遇到问题。我希望最终用户拥有的权限是:读取某个已定义前缀中的对象将对象写入相同定义的前缀列出驻留在定义的前缀中的所有对象我设法让读写正常工作，但无论我尝试什么，列表访问都无法正常工作。这是我最接近时使用的Ruby代码:AWS::STS::Policy.newdo|policy|policy.allow(a

  9. ruby-on-rails - 如果是正数，则使用 "+"前缀数字 - Ruby/Rails 4 - 2

    我想知道传统的Rails方法和Ruby方法是在数字前面加上一个“+”sybmol(如果它是正数)。例子:应该输出:+5默认情况下，负数会正确显示:输出:-3我知道我可以做类似下面的事情:0)?'+':''%>但我不喜欢那样。在Ruby和Rails中执行此操作的好方法是什么，或者如果它们相同，则对两者执行此操作的好方法是什么？ 最佳答案 查看sprintfmethodsprintf("%+d",123)1.9.3-p392:005>sprintf("%+d",123)=>"+123"1.9.3-p392:008>sprintf("%+

  10. Ruby:如何将数组的元素与前缀连接在一起？ - 2

    我有一个这样的数组:["marblecake","also","the",1337]我想取回一个字符串，该字符串包含以某个指定字符串为前缀的数组的每个元素，然后由另一个指定字符串连接在一起。例如，["marblecake","also","the",1337].join_with_prefix("%","__")应该导致#=>%marblecake__%also__%the__%1337我该怎么做？ 最佳答案 如果你的数组在a中，那么这个单行代码就可以了a.map{|k|"%#{k}"}.join("_")您可以轻松地将它放入您自己

随机推荐