Arrays give O(1) index access — append/pop end is O(1), insert/remove middle is O(n) due to shifting.
Arrays
# Contiguous memory, O(1) index access
# Python list (dynamic array)
arr = [1, 2, 3, 4, 5]
# Operations
arr[2] # O(1) - random access
arr.append(6) # O(1) amortised
arr.pop() # O(1)
arr.insert(0,0) # O(n) - shifts all elements
arr.pop(0) # O(n) - shifts all elements
len(arr) # O(1)
for x in arr: pass # O(n)
# Slice - creates a copy O(k)
arr[1:4] # elements at index 1,2,3
# 2D array
matrix = [[0]*n for _ in range(m)]
matrix[i][j] # O(1) access
# Common patterns
# Prefix sum for range queries O(1) after O(n) build
prefix = [0] * (len(arr)+1)
for i,v in enumerate(arr):
prefix[i+1] = prefix[i] + v
range_sum = prefix[r+1] - prefix[l] # sum arr[l..r]