算法基础之二分与前缀和 day 6

发布时间:2024年01月06日

二分

二分法是我们在高中数学就学习过的一种思想,他也是一种效率较高的查找算法,在编写代码的过程中,初学者很容易就会陷入死循环

二分的基本步骤如下

第一步是需要确定一个区间,使得我们的目标值一定是在区间中出现的

第二步需要确定一个性质,使得这个性质满足两点,第一点是可以根据这个性质把这个区间分为左和右连续的两段,第二点是我们最终的答案一定是二分的某一个分界点(绝大多数)

整数二分是很容易出现死循环的一种情况,因为整数是离散的,因此对应的答案在边界的情况也是两种

屏幕截图 2024-01-06 151802.png

其实相对应的,我们也可以将二分分为两大类,一种是答案在左边的终点,另一种是答案在右边的起点

我们来具体看一下这两种问题是如何二分的

第一类

目标值在红色区间的右端点

我们把区间进行标注,如图

屏幕截图 2024-01-06 152155.png

M是L和R的中点,其实就把区间[L,R]分成[L,M-1]和[M,R]

分成两段之后,我们只需要判断M的颜色(性质),如果是在红色区间,就说明目标值一定在绿色区间[M,R]内,否则说明目标值在红色区间[L,M-1]内

对应到代码上,我们可以这样写

while (L < R)
{
    M = (L + R + 1) / 2;
    if (M == '红')
        L = M;
    else
        R = M - 1;
}

这里需要注意的就是,当答案在左边区间的最后一位时,由于C/C++会自动下取整,这里算中点时就需要补上1,这样就不会漏判(死循环)了,当然这里也可以更改判断条件(例如L<=R),同样也不会出现死循环

这里有个简单的判断是否需要补上1,就是看我们在判断的时候如果写的是L=M,加上1就可以了

第二类

目标值是绿色区间的左端点

将[L,R]分成[L,M]和[M+1,R],如果M是绿色,说明目标值在红色区间[L,M],否则就是在绿色区间[M+1,R]

这里我们可以给出相应的代码

while (L < R)
{
    M = (L + R) / 2;
    if (M == '绿')
        R = M;
    else
        L = M + 1;
}

同样的,我们也是只要看判断之后的赋值语句即可,当L = M时,则需要加上1,当R = M时,则不需要加

前缀和

前缀和其实是一种快捷的求和的思想,是用于求一个静态区间的任意位置之间的所有数的和的思想

这里我们直接结合最基础的例题来理解

原题链接

795. 前缀和

题目描述

输入一个长度为 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 

题目分析

这里就是给出一个静态序列,有m次询问,每次给一对l和r,需要分别输出从l到r的总和

如果我们暴力做的话,就是每一次都需要从l加到r,并且每一次循环都是O(n)的时间复杂度

一旦当询问次数较大时,时间效率就会非常低

那么这时我们就会需要用到前缀和的思想,他非常的基础和重要,也是笔者最先开始学习的算法之一

我们把之前的那个静态序列标记为 a i a_i ai?,表示第i项,然后我们来构建一个新的序列 s i s_i si?,代表他是原序列中前i个数字的和

其中 s i = a 1 + a 2 + ? + a i s_i = a_1 + a2 + \dots + a_i si?=a1?+a2+?+ai?

特殊规定 s 0 = 0 s_0 = 0 s0?=0

这样我们就可以发现一个规律

s i = s i ? 1 + a i s_i = s_{i-1} + a_i si?=si?1?+ai?

我们可以根据这个公式递推出s序列中的所有数字

for(int i = 1; i <= n; i++)
{
    s[i] = s[i-1] + a[i];
}

这一步骤就叫做前缀和,也是我们之后求和的预处理工作

当我们想算从l到r的和时可以这样 a l + a l + 1 + a l + 2 + ? + a r a_l + a_{l+1} + a_{l+2} + \dots + a_r al?+al+1?+al+2?+?+ar?

= a 1 + a 2 + ? + a l ? 1 + a l + a l + 1 + a l + 2 + ? + a r ? a 1 ? a 2 ? ? ? a l ? 1 = a_1 + a_2 + \dots + a_{l-1} + a_l + a_{l+1} + a_{l+2} + \dots + a_r - a_1 - a_2 - \dots - a_{l-1} =a1?+a2?+?+al?1?+al?+al+1?+al+2?+?+ar??a1??a2????al?1?

= s r ? s l ? 1 = s_r - s_{l-1} =sr??sl?1?

所以当我们预处理结束之后,我们只需要计算两个数的差即可,这样的时间复杂度就达到了O(1),是质的飞跃

对于计算区间和还有其他的方法,例如树状数组和线段树,这个我们以后会讲解,而对于前缀和来说,他的局限性就在于序列只能是静态的序列,一旦其中的某个数值被修改,就需要重新计算前缀和,而树状数组和线段树是可以实现边查边算的

示例代码

#include<iostream>
using namespace std;

const int N = 1e5+10; // 数据范围
int n,m;
long long arr[N]; // 原数组
long long pre[N]; // 前缀和数组

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) // 数据输入
    {
        cin>>arr[i];
        pre[i] = pre[i-1] + arr[i]; // 前缀和初始化
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<pre[r] - pre[l-1]<<'\n';
    }
    return 0;
}
文章来源:https://blog.csdn.net/ye_yumo/article/details/135427942
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。