Peaks in Array

Problem Description

A peak in an array arr is an element that is greater than its previous and next element in arr. You are given an integer array nums and a 2D integer array queries. You have to process queries of two types:

1. Determine the count of peak elements in the subarray nums[l_i..r_i].
2. Change nums[index_i] to val_i. Return an array containing the results of the first type of queries in order.

Key Insights

• Peaks cannot be the first or last element of the array or subarray.
• Efficiently counting peaks is crucial due to the constraints (up to 100,000 elements and queries).
• Updates to the array can affect multiple potential peaks.

Space and Time Complexity

Time Complexity: O(n + q * log(n)) for processing all queries, where n is the number of elements in nums and q is the number of queries. Space Complexity: O(n) for storing peak information if using an auxiliary data structure.

Solution

To efficiently handle the queries, we can use a Segment Tree or Binary Indexed Tree (Fenwick Tree) to maintain and query the number of peaks.

1. Initially, we can calculate the peaks in the array and store their counts.
2. For type 1 queries, we query the segment tree for the count of peaks in the specified range.
3. For type 2 queries, we update the array and check if the update affects any peaks (the element itself or its neighbors).

Code Solutions