区間和

🌈 羅東彬のビデオを見て書いたのです
https://www.youtube.com/watch?v=rI8NRQsAS_s

ダブルポインタ

N個の数字には,mのすべての場合の数を和とする問題がある.

この場合,上述したように,ある点で始点を決め,すべての場合を考慮するとO(N^2)の時間的複雑さが生じる.
100万個のデータがあれば、横暴な時間が必要です.
二重ポインタを用いてO(n)時間で問題を解決できた.

ダブルポインタ

リストに順番にアクセスする必要がある場合、2点を使用して位置を記録する方法

始点(start)と終点(end)を最初の要素のインデックスに指定します.

現在の部分とMに等しいとカウントダウンします.

の現在の部分とM以下の場合、endは1増加する.

の現在の部分とMより大きい場合、startは1増加する.

すべての状況を確認する前に、プロセスを2～4回繰り返します.

二重ポインタの例)[BOJ 2003]数量の和2

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))

l, r = 0, 0
answer, hap = 0, 0

# l을 차례대로 증가시키며 반복
for l in range(n):
    # r을 가능한만큼 움직이기
    while hap < m and r < n:
        hap += nums[r]
        r += 1
    # 부분 합이 m일 때 카운트 증가
    if hap == m:
        answer += 1
    # m보다 hap이 크거나 같으므로 l 한칸 이동 
    hap -= nums[l]

print(answer)

区間和(Prefix Sum)

N個からなる数列がある場合、与えられたM個の範囲から全てのデータの和を求めることができる.
この場合,区間和を用いてO(N+M)で問題を解くことができる.

区間和(Prefix Sum)

複数の高速区間和を求める場合、テーブルを作成し、そのテーブルを使用してそれぞれ和を求める方法.

Prefix Sumが計算され、アレイPに格納される.
✨ P[i]= i번째 인덱스까지의 합

個のM個の問合せ情報を確認した場合、区間和はP[R]-P[L-1]となる.

ゾーンマージの例)[BOJ 11659]区間と4を求める

import sys
input = sys.stdin.readline

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))
prefix = [0]
curr = 0

for n in nums:
    curr += n
    prefix.append(curr)

for _ in range(m):
    i, j = map(int,input().rsplit())
    print(prefix[j]-prefix[i-1])