<p>A <strong>peak</strong> in an array <code>arr</code> is an element that is <strong>greater</strong> than its previous and next element in <code>arr</code>.</p>

<p>You are given an integer array <code>nums</code> and a 2D integer array <code>queries</code>.</p>

<p>You have to process queries of two types:</p>

<ul>
	<li><code>queries[i] = [1, l<sub>i</sub>, r<sub>i</sub>]</code>, determine the count of <strong>peak</strong> elements in the <span data-keyword="subarray">subarray</span> <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.<!-- notionvc: 73b20b7c-e1ab-4dac-86d0-13761094a9ae --></li>
	<li><code>queries[i] = [2, index<sub>i</sub>, val<sub>i</sub>]</code>, change <code>nums[index<sub>i</sub>]</code> to <code><font face="monospace">val<sub>i</sub></font></code>.</li>
</ul>

<p>Return an array <code>answer</code> containing the results of the queries of the first type in order.<!-- notionvc: a9ccef22-4061-4b5a-b4cc-a2b2a0e12f30 --></p>

<p><strong>Notes:</strong></p>

<ul>
	<li>The <strong>first</strong> and the <strong>last</strong> element of an array or a subarray<!-- notionvc: fcffef72-deb5-47cb-8719-3a3790102f73 --> <strong>cannot</strong> be a peak.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0]</span></p>

<p><strong>Explanation:</strong></p>

<p>First query: We change <code>nums[3]</code> to 4 and <code>nums</code> becomes <code>[3,1,4,4,5]</code>.</p>

<p>Second query: The number of peaks in the <code>[3,1,4,4,5]</code> is 0.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,1]</span></p>

<p><strong>Explanation:</strong></p>

<p>First query: <code>nums[2]</code> should become 4, but it is already set to 4.</p>

<p>Second query: The number of peaks in the <code>[4,1,4]</code> is 0.</p>

<p>Third query: The second 4 is a peak in the <code>[4,1,4,2,1]</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i][0] == 1</code> or <code>queries[i][0] == 2</code></li>
	<li>For all <code>i</code> that:
	<ul>
		<li><code>queries[i][0] == 1</code>: <code>0 &lt;= queries[i][1] &lt;= queries[i][2] &lt;= nums.length - 1</code></li>
		<li><code>queries[i][0] == 2</code>: <code>0 &lt;= queries[i][1] &lt;= nums.length - 1</code>, <code>1 &lt;= queries[i][2] &lt;= 10<sup>5</sup></code></li>
	</ul>
	</li>
</ul>

class Solution:
    def countOfPeaks(self, nums, queries):
        n = len(nums)
        # Segment Tree for peak counts
        peak_tree = [0] * (4 * n)

        def is_peak(i):
            """Helper function to determine if element at index i is a peak."""
            return 0 < i < n - 1 and nums[i] > nums[i - 1] and nums[i] > nums[i + 1]

        def build_tree(node, start, end):
            """Build the segment tree based on peak counts."""
            if start == end:
                peak_tree[node] = 1 if is_peak(start) else 0
            else:
                mid = (start + end) // 2
                build_tree(2 * node + 1, start, mid)
                build_tree(2 * node + 2, mid + 1, end)
                peak_tree[node] = peak_tree[2 * node + 1] + peak_tree[2 * node + 2]

        def update_tree(node, start, end, idx):
            """Update the segment tree when a value in nums changes."""
            if start == end:
                peak_tree[node] = 1 if is_peak(start) else 0
            else:
                mid = (start + end) // 2
                if start <= idx <= mid:
                    update_tree(2 * node + 1, start, mid, idx)
                else:
                    update_tree(2 * node + 2, mid + 1, end, idx)
                peak_tree[node] = peak_tree[2 * node + 1] + peak_tree[2 * node + 2]

        def query_tree(node, start, end, l, r):
            """Query the number of peaks in the subarray nums[l..r]."""
            if r < start or end < l:
                return 0
            if l <= start and end <= r:
                return peak_tree[node]
            mid = (start + end) // 2
            left_query = query_tree(2 * node + 1, start, mid, l, r)
            right_query = query_tree(2 * node + 2, mid + 1, end, l, r)
            return left_query + right_query

        # Build the initial segment tree
        build_tree(0, 0, n - 1)
        results = []

        for query in queries:
            if query[0] == 1:  # Count peaks in the subarray nums[li..ri]
                li, ri = query[1], query[2]
                if ri - li < 2:  # No peaks possible if the range is less than 3 elements
                    results.append(0)
                else:
                    results.append(query_tree(0, 0, n - 1, li + 1, ri - 1))
            elif query[0] == 2:  # Update nums[indexi] to vali
                indexi, vali = query[1], query[2]
                nums[indexi] = vali
                # Update the relevant indices in the segment tree
                for i in range(max(1, indexi - 1), min(n - 1, indexi + 1) + 1):
                    update_tree(0, 0, n - 1, i)

        return results


82900