主頁 >  其他 > 前綴和(區間和)

前綴和(區間和)

2021-09-15 13:11:35 其他

前綴和

Definition

?對于一個陣列A,有另一個陣列Sum,
s . t . S u m [ n ] = ∑ i = 1 n A [ i ] , n ∈ [ 1 , s i z e o f ( A ) ] , s.t.\quad Sum[n] = \sum\limits _{i=1}^n A[i] ,\quad n \in [ 1, sizeof(A)], s.t.Sum[n]=i=1n?A[i],n[1,sizeof(A)],
我們稱陣列Sum為陣列A的前綴和


Let’s have an example:

區間和
給出一個長度為n的整數序列,給出m個詢問, 詢問的形式為[a,b],請你快速回答第a到第b個數字之和(也就是區間a到b中所有數字之和),
輸入格式:
第一行,兩個整數n和m,表示有n個整數,m個詢問,
第二行,n個空格間隔的整數,表示序列中每個數字的值,
接下來m行,每行兩個整數a,b,表示詢問的區間,
輸出格式:
m行,每行一個整數,對應一個詢問的答案,
樣例輸入:
7 3
2 3 1 7 8 -5 9
1 3
2 6
4 7
樣例輸出:
6
14
19
資料范圍:
1<=n<=100000
1<=m<=50000
-10000<=序列中的每個數字的值<=10000

  • 方法一:暴力列舉
int n, m, Sum;
int A[100003];
int main() {
	scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; ++ i)scanf("%d",&A[i]);   //將n個數字存到A陣列中
    for(int i = 1; i <= m; ++ i) {          //處理m個詢問
    	int x, y;
        scanf("%d%d",&x, &y);              //詢問第x到第y個數之和
        Sum = 0;                           //Sum賦初值,記錄x到y之和
        for(int j = x; j <= y; ++ j)Sum += A[j];
        printf("%d\n",Sum);                  //輸出每次詢問的結果
    }
    return 0;
}

顯然這種方法最容易想到,但耗時卻很長,時間復雜度達到了 O ( n 2 ) O(n^2) O(n2),在數字極大,詢問次數極多時,顯得有些不切實際了,

既然我們前文提到了前綴和,那么它與這樣的問題有何聯系呢?

Application

??如前文所述, S u m [ n ] = ∑ i = 1 n A [ i ] Sum[n] = \sum\limits _{i=1}^n A[i] Sum[n]=i=1n?A[i],我們可以推得:

下標1234567
陣列A23178-59
陣列Sum25613211625

∑ i = 3 6 A [ i ] = A [ 3 ] + A [ 4 ] + A [ 5 ] + A [ 6 ] = S u m [ 6 ] ? S u m [ 2 ] \sum\limits _{i=3}^6 A[i] = A[3]+A[4]+A[5]+A[6] \\ =Sum[6] - Sum[2] i=36?A[i]=A[3]+A[4]+A[5]+A[6]=Sum[6]?Sum[2]
可提煉為,對于每一次詢問區間[a, b]的和:
∑ i = a b A [ i ] = S u m [ b ] ? S u m [ a ? 1 ] , a , b ∈ [ 1 , s i z e o f ( A ) ] \sum\limits _{i=a}^b A[i] = Sum[b] - Sum[a-1],\quad a, b\in[1, sizeof(A)] i=ab?A[i]=Sum[b]?Sum[a?1],a,b[1,sizeof(A)]
??離線的陣列讓每次詢問的時間復雜度都是 O ( 1 ) O(1) O(1)
??以上展示的為一維前綴和,高維前綴和請以此類推,

  • 方法二:前綴和
int n, m;
int A[100003], Sum[100003];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &A[i]);
		Sum[i] = A[i] + Sum[i - 1];  //輸入時初始化Sum陣列
	}
	for (int i = 1; i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d", Sum[y] - Sum[x - 1]);
	}
	return 0;
}

顯然,這種方法犧牲空間優化時間,將在線查詢離線化,大大減少了計算的時間,將時間復雜度從 O ( n 2 ) O(n^2) O(n2)優化為 O ( n ) O(n) O(n),十分巧妙,


Examples

Ex.1

炸彈人
益智游戲《炸彈人》的地圖是一個n*m的方格矩陣,有的方格是空地,有的方格是障礙物,有的方格里是游戲玩家們操控的“炸彈人”,
玩家可以在空地上安放炸彈,炸彈爆炸的火焰呈十字型,并可延伸到無限遠出,只有遇到了障礙物才會停下來,火焰所經過的方格內如果有“炸彈人”,該“炸彈人”會被炸死,每炸死一個“炸彈人”,玩家就會獲得一分,
現在你手中只剩下一顆炸彈了,你可以把這顆炸彈安放在任何空地上,問,安放在什么位置,你才能獲得最大得分?
輸入格式
第一行,兩個空格間隔的整數n和m,表示有一個n*m的地圖,
接下來是一個由整數構成的n*m的矩陣,表示當前地圖的情況,其中數字0表示空地,數字1表示“炸彈人”,數字2表示障礙物,數字間以空格間隔,
輸出格式
一個整數,表示最大的得分,
樣例輸入
5 5
0 1 0 1 2
0 1 0 0 1
1 0 1 2 1
0 1 0 0 1
0 2 1 1 0

參考代碼(主要演算法部分):

轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/300350.html

標籤:其他

上一篇:51nod3152 取數游戲

下一篇:返回列表

標籤雲
其他(117369) Java(12752) Python(11473) C(7255) 區塊鏈(6950) JavaScript(6526) 基礎類(6313) AI(5933) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4106) MySQL(3897) Linux(3312) C語言(3288) C++語言(3117) Java相關(2746) 疑難問題(2699) 單片機工控(2479) Web開發(1951) 網絡通信(1793) 數據庫相關(1767) VB基礎類(1755) 開發(1646) 系統維護與使用區(1617) PHP(1580) 基礎和管理(1579) JavaEE(1566) .NETCore(1555) 專題技術討論區(1515) C++(1508) Windows客戶端使用(1484) HtmlCss(1446) ASP.NET(1381) Unity3D(1354) VCL組件開發及應用(1353) HTML(CSS)(1220) 其他技術討論專區(1200) WindowsServer(1191) 交換及路由技術(1149) 語言基礎算法系統設計(1133) WindowsSDKAPI(1124) .NET技术(1100) 界面(1083) JavaSE(1075) Qt(1045) 新手樂園(1016) VBA(993) 其他開發語言(947) 新技術前沿(898) HTML5(888) Go(885) 硬件設計(872) 區塊鏈技術(860) 網絡編程(857) 非技術版(846) 一般軟件使用(839) 網絡協議與配置(835) Eclipse(790) Spark(750) 下載資源懸賞專區(743)
熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種:三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看,三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看,三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統,“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及:虛擬機CentOs下執行 yum -y install lrzsz命令,出現錯誤:鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示:其實很簡單,往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號, sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求,SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生, 2020-08-28 16:18:25 分類專欄: kail 網路安全 linux 文章標簽: linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么? 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼: #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘(北斗授時服務器)讓網路資料更精準

    北斗電力時鐘(北斗授時服務器)讓網路資料更精準 北斗電力時鐘(北斗授時服務器)讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年,資訊技術的得了快速發展,互聯網在逐漸普及,其在人們生活和生產中都得到了廣泛應用,并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用,一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub:https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺,后來才有了CTFHub。 感覺不論是網頁UI設計,還是題目質量,賽事跟蹤,工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解(net user / type /md /rd/ dir /cd /net use copy、批處理 等) 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝,密碼啊破解03Linux常用命令04LAMP 01LINUX windows: win03 8 12 16 19 配置不繁瑣 Linux:redhat,centos(紅帽社區版),Ubuntu server,suse unix:金融機構,證券,銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 (POST注入/XSS漏洞上傳)3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題,描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 前綴和(區間和)

    介紹了一種叫做“前綴和”的陣列,通過對比的手段展示了它在離線多次區間和查詢的優化性。...

    uj5u.com 2021-09-15 13:11:35 more
  • 51nod3152 取數游戲

    3152 取數游戲有這樣一個取數游戲,給出個正整數(2 <= n <= 100000),在其中選出個數,使得他們的gcd(最大公約數)最大,求這個最大的gcd。輸入第一行一個整數n第二行n個正整數輸出一個一個數表示答案資料范圍10% 2 <= n <= 1030% 2 <= n <= 30060% 2 <= n <= 5000100% 2 <= n <= 100000輸入樣例輸入樣例1:66...

    uj5u.com 2021-09-15 13:11:27 more
  • Pico VR 在Unity里通過S/N號進行加密

    這個是判斷陳述句//判斷當前設備序列號是否在自定義的序列號當中。if (Pvr_UnitySDKAPI.PlatformSettings.UPvr_IsCurrentDeviceValid().Equals(Pvr_UnitySDKPlatformSetting.simulationType.Valid)) { //Debug.Log("進入下個場景"); } else...

    uj5u.com 2021-09-15 13:11:05 more
  • Windows 獲取 Ubuntu 虛擬機中的截圖

    其實,這個事情的起因很簡單。我就想在 Windows 主機中使用一些從 Ubuntu 虛擬機中截到的圖片。上網搜索,發現虛擬機的 Unity 模式是最簡單的方法。然而我安裝的是 Linux 客戶機,不支持 Unity 模式。條件允許的小伙伴,可以參照這個方法 進入Unity 模式喲(其實就是點下 Unity 就行)。Linux系統下 Ctrl + PrtSc 就可以將截取的整個螢屏的圖片保存在剪切板上,之后 Ctrl + V 就可以了。虛擬機怎么樣使用Unity模式Linux系統如何截圖.....

    uj5u.com 2021-09-15 13:10:41 more
  • 【Python】經典實作俄羅斯輪賭,你和你的小伙伴可以玩兒的解壓小游

    #俄羅斯輪賭這個經典小游戲相信各位也是很熟知的,那么今天就給大家帶來了俄羅斯輪賭,你和小伙伴在這時候就可以來玩一玩,解決一下無法言說的事情!!!詳情如下所示:import randomimport timegum=[] #模擬彈倉for i in range(6): gum.append(0) #模擬空槍pos=random.randint(0,5)gum[pos]=1print(gum)i=0people=['阿波羅','秦始皇']i=0for ....

    uj5u.com 2021-09-15 13:10:31 more
  • Pygame實戰:據說這是史上最難掃雷游戲,沒有之一!你們感受下......

    導語每日游戲更新系列——今天帶大家來看看掃雷小游戲!它是許多人接觸到的第一款游戲,大概也是廣大辦公族和無網學生無聊時消遣的最佳游戲。在那些還沒有網(被切斷網)的歲月,掃雷曾陪伴無數人度過了他們的童年。你的最佳紀錄是多少了?對于許多90后、00后來說,掃雷這個電腦上自帶的小游戲早就變成古早的歷史,再一次提到掃雷這個名字的時候,對許多人來說,仿佛就是上世紀的事情了。?就像是偶爾點開微信的跳一跳小游戲,發現排行榜上還有人在孤獨的霸榜一樣。已經2021年了,還有許多90后、00后堅守在掃雷這...

    uj5u.com 2021-09-15 13:09:22 more
  • FastAPI 學習之路(二)

    之前的文章已經介紹了如何安裝,以及簡單的使用,這篇文章呢,我們就不去分享如何安裝對應的包了。 我們如何去撰寫呢,其實很簡單,按照下面的步驟,一個簡單的基于fastapi的介面就撰寫完畢。 首先:創建一個main.py 第一步:匯入 from fastapi import FastAPI 第二步:實體 ......

    uj5u.com 2021-09-15 12:43:49 more
  • FastAPI 學習之路(二)

    之前的文章已經介紹了如何安裝,以及簡單的使用,這篇文章呢,我們就不去分享如何安裝對應的包了。 我們如何去撰寫呢,其實很簡單,按照下面的步驟,一個簡單的基于fastapi的介面就撰寫完畢。 首先:創建一個main.py 第一步:匯入 from fastapi import FastAPI 第二步:實體 ......

    uj5u.com 2021-09-15 12:14:50 more
  • RSA及其證明 [原創]

    描述RSA的實作步驟介紹文章非常多,但說明并證明其原理,并進而討論為什么這樣設計的文章不多。本人才疏學淺,不敢說理解了R.S.A.三位泰斗的設計初衷,簡單就自己的理解寫一寫,博大家一笑。 以下原創內容歡迎網友轉載,但請注明出處: https://www.cnblogs.com/helesheng 一 ......

    uj5u.com 2021-09-15 12:11:11 more
  • [第二十篇]&mdash;&mdash;Docker 安裝 Tomcat之Spring Cloud直播

    Docker 安裝 Tomcat方法一、docker pull tomcat查找Docker Hub上的 Tomcat 鏡像:可以通過 Sort by 查看其他版本的 tomcat,默認是最新版本tomcat:latest。此外,我們還可以在控制臺使用docker search tomcat命令來查看可用版本:[email protected]:~/tomcat$dockersearchtomcatNAMEDESCRIPTION......

    uj5u.com 2021-09-15 11:33:50 more