1/17
Loading...
📚区間クエリが何度も!
日別訪問者: [5, 8, 6, 3, 7, 9, 4] 司書が「l日~r日の合計?」を 一日に何十回も尋ねます。 毎回足すのは遅すぎます!
Loading...
日別訪問者: [5, 8, 6, 3, 7, 9, 4] 司書が「l日~r日の合計?」を 一日に何十回も尋ねます。 毎回足すのは遅すぎます!
あなたは地域図書館の運営担当者です。曜日別の訪問者数の配列が与えられ、司書たちは「l日目からr日目まで合計何人来ましたか?」という質問を一日に何十回もします。質問のたびに最初から足すのは遅すぎます。事前に累積和配列を作っておけば、どんな区間でも引き算一回で即座に答えられます。
visitors = [5, 8, 6, 3, 7, 9, 4], queries = [[2, 5], [0, 2], [4, 6]]
[25, 19, 20]
累積和: prefix = [0, 5, 13, 19, 22, 29, 38, 42] • [2, 5]: prefix[6] - prefix[2] = 38 - 13 = 25 (6+3+7+9) • [0, 2]: prefix[3] - prefix[0] = 19 - 0 = 19 (5+8+6) • [4, 6]: prefix[7] - prefix[4] = 42 - 22 = 20 (7+9+4)
visitors = [10, 0, 4, 6], queries = [[0, 3], [1, 1]]
[20, 0]
累積和: prefix = [0, 10, 10, 14, 20] • [0, 3]: prefix[4] - prefix[0] = 20 - 0 = 20 (全体の和) • [1, 1]: prefix[2] - prefix[1] = 10 - 10 = 0 (休館日!)