基础算法篇

您所在的位置：网站首页 › 差分运算的作用 › 基础算法篇

基础算法篇

2022-11-17 15:50| 来源: 网络整理| 查看: 265

本次我们介绍基础算法中的前缀和与差分，我们会从下面几个角度来介绍前缀和与差分：

前缀和介绍一维前缀和二维前缀和差分介绍一维差分二维差分前缀和介绍

首先我们来简单介绍一下前缀和：

我们首先定义一个长度为n的数组，然后我们希望求这个数组的部分长度的总和

如果正常采用我们的for循环来遍历一遍的话：

复杂度为O（n）

这时如果我们提前将这些数据保存起来，在多次查询时就会方便很多：

我们将数组的第i个值定义为ai我们将数组的前n个值的和定义为Sn其实就是类似于我们数学上的基本算法

我们如果想要求解某一部分的值，只需要用S进行删减即可：

// sum[l,r] = S[r] - S[l-1]

这里我们做一个小小的细节处理：

// 由于我们需要S[r] - S[l-1]完成计算 // 那么当我们的l=0时，我们需要S[r]-S[-1],这明显是不可行的，但是如果我们将整体往前移动一位 // 我们直接让数组从1开始，让S数组也从1开始，并将S[0]=0，这样我们在计算[1,k]之间的数时就可以直接使用S[r]-S[l-1]了一维前缀和

题型：

输入数组长度和一组数组，输入需要查询的前缀和次数，输入需要查询的区块下标，返回对应的sum值

代码展示：

import java.util.Scanner; public class PrefixSum { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入数组长度和查询次数 int n = scanner.nextInt(); int k = scanner.nextInt(); // 输入数组内容 int[] arr = new int[n+1]; for (int i = 1; i

【本文地址】

基础算法篇

基础算法篇

今日新闻

推荐新闻