如何搭建手机网站,建网站平台哪家好,深圳公司网站设计,做卖东西的网站个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【牛客网刷题】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【牛客网刷题】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
题目描述 给定一个长度为n的数组a1,a2,…,an。 接下来有q次查询, 每次查询有两个参数l, r。 对于每个询问, 请输出al,al1,…ar。
输入描述 第一行包含两个整数n和q。 第二行包含n个整数, 表示a1,a2,…,an。 接下来q行,每行包含两个整数l和r。
1≤n,q≤ 1 0 5 10^{5} 105 - 1 0 9 10^{9} 109 ≤ a[i] ≤ 1 0 9 10^{9} 109 1 ≤ l ≤ r ≤ n
输出描述 输出q行,每行代表一次查询的结果。
示例 输出 3 2 1 2 4 1 2 2 3 2️⃣题目解析
前缀和的思想是通过提前计算和存储每个位置前的元素之和以便在需要时能够快速获取。通过预先计算并存储前缀和我们可以在O(1)的时间复杂度内获得任意区间内元素的和而不需要每次都重新计算。对于前缀和问题的话总共分为两步骤①创建一个前缀和数组②使用前缀和数组。
状态表示
dp[i]表示数组从[1,i]之间所有元素的和。
状态转移方程
dp[i] dp[i - 1] arr[i]
关于本题目的时间复杂度如下
时间复杂度O(q) O(n)。O(q)是用来查询q次询问。而O(n)用来创建前缀和数组。
3️⃣解题代码
#includeiostream
#includevector
using namespace std;int main()
{int n,q;cin n q;vectorlong long arr(n 1),dp(n 1);for(int i 1;i n;i)cin arr[i];for(int i 1;i n;i)dp[i] dp[i - 1] arr[i];while(q--){int l, r;cin l r;cout dp[r] - dp[l - 1] endl;}return 0;
}最后就是代码通过啦
