- Choose the aggregate stored for each interval or prefix.
- Build or initialize the structure from the input.
- Apply updates and combine the affected nodes to answer each query.
Code notes
- 66 lines of Python from the credited upstream file 3187.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Count the build once, then multiply the logarithmic update or query path by the number of operations.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class FenwickTree:2 def __init__(self, n: int):3 self.sums = [0] * (n + 1)4 5 def add(self, i: int, delta: int) -> None:6 while i < len(self.sums):7 self.sums[i] += delta8 i += FenwickTree.lowbit(i)9 10 def get(self, i: int) -> int:11 summ = 012 while i > 0:13 summ += self.sums[i]14 i -= FenwickTree.lowbit(i)15 return summ16 17 @staticmethod18 def lowbit(i: int) -> int:19 return i & -i20 21 22class Solution:23 def countOfPeaks(24 self,25 nums: list[int],26 queries:27 list[list[int]],28 ) -> list[int]:29 ans = []30 peak = [0] + [int(a < b > c)31 for a, b, c in zip(nums[:-2], nums[1:-1], nums[2:])] + [0]32 tree = FenwickTree(len(peak))33 34 for i, p in enumerate(peak):35 tree.add(i + 1, p)36 37 def update(i: int) -> None:38 """39 Update the peak array and Fenwick tree if the peak status of nums[i]40 changes.41 """42 newPeak = self._isPeak(nums, i)43 if newPeak != peak[i]:44 tree.add(i + 1, newPeak - peak[i])45 peak[i] = newPeak46 47 for query in queries:48 if query[0] == 1:49 l = query[1]50 r = query[2]51 ans.append(0 if r - l < 2 else tree.get(r) - tree.get(l + 1))52 elif query[0] == 2:53 index = query[1]54 val = query[2]55 nums[index] = val56 update(index)57 if index > 0:58 update(index - 1)59 if index + 1 < len(nums):60 update(index + 1)61 62 return ans63 64 def _isPeak(self, nums: list[int], i: int) -> bool:65 return i > 0 and i + 1 < len(nums) and nums[i - 1] < nums[i] > nums[i + 1]66