The Peaks in Array problem supports two operations on an array: (1) update a single element, and (2) query the number of peaks in a range [l, r]. A peak is an element strictly greater than both its neighbors. This hard coding problem requires an efficient data structure for range peak queries under point updates. The array, binary indexed tree, and segment tree interview pattern is the core.
Siemens asks this hard design problem because peaks are a "neighborhood" property — each element depends on its neighbors. Updates affect up to 3 peak statuses (the updated element and its immediate neighbors). A segment tree or binary indexed tree tracks peak counts per index, supporting O(log n) update and O(log n) range sum query.
Segment tree or BIT for range peak sum. Precompute isPeak[i] = 1 if arr[i] > arr[i-1] and arr[i] > arr[i+1], else 0. For each update at index i: recompute isPeak for indices i-1, i, i+1 (at most 3 updates to the peak array). Use a BIT/segment tree to answer range sum queries sum(isPeak[l+1..r-1]) (endpoints can't be peaks since they have only one neighbor).
arr=[1,3,1,4,2]. Peaks: index 1 (3>1,3>1)=peak, index 3 (4>1,4>2)=peak. isPeak=[0,1,0,1,0]. Query [1,4]: sum(isPeak[2..3])=isPeak[2]+isPeak[3]=0+1=1 peak. Update index 2 to 5: arr=[1,3,5,4,2]. Recompute isPeak[1]=(3>1,3<5)=not peak. isPeak[2]=(5>3,5>4)=peak. isPeak[3]=(4<5)=not peak. Updated isPeak=[0,0,1,0,0].
Peak counting with updates requires understanding that peaks are "local" (3-element windows). Each point update affects at most 3 peak statuses. The segment tree over the isPeak array supports both range sum queries (count peaks in range) and point updates (recompute 3 values). Practice similar "neighborhood property" segment tree problems: "count valleys in range," "count local extrema under updates."
