[アルゴリズム]求伯準-区間と4

白駿-区間と4を求めます

説明する

import sys

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

acc_num = [0] * (len(nums) + 1)

for i in range(1, len(nums) + 1):
    acc_num[i] = acc_num[i-1] + nums[i -1]

for m in range(M):
    start_idx, end_idx = list(map(int, sys.stdin.readline().split()))
    print(acc_num[end_idx] - acc_num[start_idx - 1])

コンセプト

区間合併に関するアルゴリズムについてお話しします.
区間と原O(N)の時間でしか解決できないことを求めます.
効率の問題では,区間統合の問題がしばしば発生する.また,O(N)で区間和を求めると効率の問題を通過できない.少なくともO(logn)で区間和を求めてこそ効率問題を通過することができる.
もしあなたが後であなたに教える簡単な方法を知らないならば、あなたはいくつかの厄介な方法で区間と(logn)を求める必要があるかもしれませんが、もしあなたが今私に教えてくれた方法ならば、あなたは簡単にO(1)で区間とを求めることができます.
その方法は「累加」を求めることです
マトリクスの累積和を以下のコードで求めてみよう

// 누적합을 구하는 코드
for(int i = 1; i<nums.length; i++){
	nums[i] += nums[i-1];
}

次の手順により、累積配列を簡単に完了できます.


累積和を求めると,現在O(1)の区間和を求めることができる.
3~10の区間和を求めることを考慮すると,累積と2を減算して求めた値である.

nums[10] - nums[2] // 기존의 3 ~ 10의 합을 구한 것이다

ただし、データが途中で変更された場合、このメソッドは使用できません.データが変化するたびに,求めた蓄積と行列は線形に変化するからである.