Jumlah Awalan dan Total Berjalan
Bangun array jumlah awalan untuk menjawab kueri jumlah rentang dalam O(1), lalu terapkan teknik ini pada masalah subarray seperti subarray dengan jumlah maksimum.
Jumlah Awalan dan Total Berjalan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Jumlah Rentang
Diberikan larik nums, Anda perlu menjawab banyak kueri dalam bentuk: berapa jumlah elemen dari indeks i hingga indeks j? Menghitung setiap kueri secara naif membutuhkan waktu O(n), sehingga k kueri membutuhkan O(n×k). Dengan larik jumlah prefiks, Anda menghitung terlebih dahulu total berjalan dalam O(n), lalu menjawab setiap kueri dalam O(1). Ini adalah salah satu teknik praperhitungan yang paling banyak digunakan dalam wawancara.
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operationsMembangun Larik Jumlah Prefiks
Definisikan prefix[i] sebagai jumlah nums[0] hingga nums[i-1] (satu slot tambahan; pergeseran indeks berbasis nol sebesar 1 membuat kasus batas lebih sederhana). Bangun larik tersebut dalam O(n) dengan satu lintasan: prefix[i] = prefix[i-1] + nums[i-1]. Kemudian kueri rentang sum(i, j) menjadi prefix[j+1] - prefix[i]: satu pengurangan yang membutuhkan O(1).
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15Jumlah Sublarik Sama dengan K
Menemukan jumlah sublarik yang jumlahnya sama dengan k adalah soal klasik yang menggabungkan peta hash dan jumlah prefiks. Gagasan utamanya: jumlah sublarik dari i hingga j sama dengan prefix[j] - prefix[i-1]. Jika kita ingin nilainya sama dengan k, maka prefix[i-1] = prefix[j] - k. Saat menelusuri dari kiri ke kanan sambil mempertahankan jumlah prefiks berjalan, kita mencari berapa kali current_sum - k telah muncul sebelumnya, sehingga semua sublarik valid dapat dihitung dalam total waktu O(n).
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])Jumlah Sublarik Maksimum dengan Prefiks
Jumlah sublarik maksimum dapat dirumuskan sebagai soal jumlah prefiks: untuk setiap indeks j, kita ingin memaksimalkan prefix[j] - prefix[i] untuk semua i < j. Nilai i yang optimal pada setiap j adalah jumlah prefiks minimum yang telah ditemukan sejauh ini. Penelusuran dari kiri ke kanan sambil melacak min_prefix membutuhkan waktu O(n). Ini setara dengan algoritme Kadane jika dilihat dari sudut pandang jumlah prefiks.
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1Jumlah Prefiks 2D untuk Kueri Kisi
Jumlah prefiks juga dapat diterapkan pada kisi 2D. Definisikan P[i][j] sebagai jumlah semua elemen dalam persegi panjang dari (0,0) hingga (i-1,j-1). Bangun dengan rumus inklusi-eksklusi: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Kemudian setiap kueri jumlah persegi panjang dari (r1,c1) hingga (r2,c2) dapat dijawab dalam O(1) menggunakan empat pengambilan nilai.
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14Total Berjalan untuk Indeks Keseimbangan
Indeks keseimbangan adalah posisi ketika jumlah elemen di sebelah kiri sama dengan jumlah elemen di sebelah kanan. Hitung terlebih dahulu jumlah total, lalu telusuri larik sambil mempertahankan jumlah kiri berjalan. Jumlah kanan adalah total - left_sum - nums[i]. Periksa kesamaan dalam O(1) untuk setiap indeks, sehingga keseluruhannya membutuhkan O(n). Ini menunjukkan bagaimana total berjalan dapat menggantikan dua larik jumlah prefiks yang terpisah.
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1Larik Hasil Kali Selain Diri Sendiri
Diberikan sebuah larik, kembalikan larik yang setiap elemennya merupakan hasil kali semua elemen lainnya. Pembagian tidak diperbolehkan. Gunakan hasil kali prefiks dan hasil kali sufiks: result[i] = (hasil kali semua elemen sebelum i) × (hasil kali semua elemen setelah i). Bangun hasil kali prefiks dalam satu lintasan dari kiri ke kanan, lalu kalikan hasilnya dengan hasil kali sufiks dalam satu lintasan dari kanan ke kiri menggunakan variabel berjalan—tidak diperlukan larik tambahan untuk sufiks.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra spaceJumlah Prefiks dengan Sisa Bagi
Beberapa soal menanyakan jumlah sublarik yang jumlahnya habis dibagi k. Dengan menggunakan jumlah prefiks modulo k: jika prefix[j] % k == prefix[i] % k, maka sum(i+1..j) habis dibagi k. Peta hash yang menghitung setiap nilai sisa saat kita menelusuri larik memberikan waktu O(n). Inisialisasi pentingnya adalah freq[0] = 1 untuk menangani sublarik yang dimulai pada indeks 0.
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)Larik Selisih untuk Pembaruan Rentang
Larik selisih adalah kebalikan dari jumlah prefiks. Diberikan sebuah larik, hitung terlebih dahulu diff[i] = nums[i] - nums[i-1]. Menambahkan x ke rentang [l, r] hanya memerlukan dua operasi O(1) pada larik selisih: diff[l] += x dan diff[r+1] -= x. Setelah semua pembaruan selesai, bangun kembali larik hasil dengan satu lintasan jumlah prefiks. Ini mengubah k pembaruan rentang dari O(n×k) menjadi O(n + k).
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]Jumlah Prefiks dalam Soal Wawancara
Jumlah prefiks muncul dalam banyak kategori soal:
- Kueri rentang — jumlah sublarik, jumlah persegi panjang
- Penghitungan sublarik — jumlah sama dengan k, habis dibagi k
- Soal hasil kali — hasil kali selain diri sendiri
- Keseimbangan — menemukan indeks poros
- Pembaruan rentang — larik selisih
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3Jumlah Berjalan dan Maksimum Berjalan
Selain jumlah prefiks, banyak soal menggunakan maksimum berjalan atau minimum berjalan yang dipertahankan dengan satu variabel. Soal waktu terbaik untuk membeli saham menggunakan harga minimum berjalan; soal menampung air hujan dari sisi kiri menggunakan tinggi maksimum kiri yang berjalan. Pola-pola ini hanya memerlukan satu lintasan dan ruang tambahan O(1), sehingga menjadi patokan utama untuk efisiensi waktu dan ruang.
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari bahwa: jumlah prefiks mengubah kueri rentang O(n) menjadi pengambilan nilai O(1) dengan menghitung terlebih dahulu jumlah kumulatif dalam satu lintasan O(n), penggabungan jumlah prefiks dengan peta hash memungkinkan solusi O(n) untuk menghitung sublarik dengan jumlah tertentu atau sifat keterbagian tertentu, dan larik selisih adalah kebalikannya: larik ini memungkinkan pembaruan rentang O(1) dengan satu lintasan pembangunan kembali melalui jumlah prefiks pada akhir proses. Selanjutnya kita akan membahas teknik dua penunjuk, dimulai dengan penunjuk dari kedua ujung.
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jumlah Awalan dan Total Berjalan” gratis?
Ya — teks lengkap “Jumlah Awalan dan Total Berjalan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jumlah Awalan dan Total Berjalan”?
Bangun array jumlah awalan untuk menjawab kueri jumlah rentang dalam O(1), lalu terapkan teknik ini pada masalah subarray seperti subarray dengan jumlah maksimum. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Jumlah Awalan dan Total Berjalan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Dasar Array dan Operasi In-Place
- Jumlah Awalan dan Total Berjalan
- Dua Pointer: Ujung Berlawanan
- Dua Pointer: Lambat dan Cepat