[python]区間と4[白駿11659]を求める

問題のショートカット
に答える
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
リストの長さ(N)は最大100000,区間和を求めるコマンド(M)は最大100000であるため,完全ナビゲーションを使用するとタイムアウトが発生するため,事前に累積を求めて[i,j]区間におけるリストの値を加算して問題を解決する.

リストスライドを使用するとタイムアウト

import sys

N, M = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
i = 0

while i < M:
    start, end = map(int, sys.stdin.readline().split())
    print(sum(num[:end]) - sum(num[:start-1]))
    i += 1

積算関数を用いて区間とリストを事前に作成し、区間と

を計算する.

import sys
from itertools import accumulate

N, M = map(int, sys.stdin.readline().split())

num = list(map(int, sys.stdin.readline().split()))
num = list(accumulate(num))
num.append(0)

i = 0
while i < M:
    start, end = map(int, sys.stdin.readline().split())
    print(num[end - 1] - num[start - 2])
    i += 1

セグメント要約テーブル生成方法2

n = int(input())
num = list(map(int, input().split()))
num_acc = [0]
i = 0
while i < n:
    num_acc.append(num_acc[-1] + num[i])
    i += 1