<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 SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0]*(4*self.n)
        self.build(arr, 0, 0, self.n-1)

    def build(self, arr, i, start, end):
        if start == end:
            self.tree[i] = arr[start]
            return
        mid = (start+end)//2
        self.build(arr, 2*i+1, start, mid)
        self.build(arr, 2*i+2, mid+1, end)
        self.tree[i] = self.tree[2*i+1] + self.tree[2*i+2]

    def update(self, i, start, end, idx, val):
        if start == end:
            self.tree[i] = val
            return
        mid = (start+end)//2
        if start <= idx <= mid:
            self.update(2*i+1, start, mid, idx, val)
        else:
            self.update(2*i+2, mid+1, end, idx, val)
        self.tree[i] = self.tree[2*i+1] + self.tree[2*i+2]
    def point_update(self, idx, val):
        self.update(0, 0, self.n-1, idx, val)

    def query(self, i, start, end, left, right):
        # If the range represented by i is outside left and right
        if right < start or left > end:
            return 0
        # Range represented by a i is completely inside the given range
        if left <= start <= end <= right:
            return self.tree[i]
        mid = (start+end)//2
        left_sum = self.query(2*i+1, start, mid, left, right)
        right_sum = self.query(2*i+2, mid+1, end, left, right)
        return left_sum + right_sum
    def range_query(self, left, right):
        return self.query(0, 0, self.n-1, left, right)

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 1)
    
    def update(self, index, value):
        while index <= self.n:
            self.tree[index] += value
            index += index & -index
    
    def query(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result
    
    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)


class Solution:
    # Time: O(n+m*log(n))
    # Space: O(n), where n, m = len(nums), len(queries)
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        
        n, m = len(nums), len(queries)

        # p[i] = 1 if nums[i] is a peak
        p = [0]*n
        for i in range(1, n-1):
            p[i] = int(nums[i-1] < nums[i] > nums[i+1])

        segment_tree = SegmentTree(p)
        
        def change(i, val):
            nums[i] = val
            if i == 0:
                p[i+1] = int(nums[i] < nums[i+1] > nums[i+2])
            elif i == 1:
                p[i] = int(nums[i-1] < nums[i] > nums[i+1])
                if i + 2 < n:
                    p[i+1] = int(nums[i] < nums[i+1] > nums[i+2]) 
            elif i == n-2:
                if i - 2 >= 0:
                    p[i-1] = int(nums[i-2] < nums[i-1] > nums[i]) 
                p[i] = int(nums[i-1] < nums[i] > nums[i+1])
            elif i == n-1:
                p[i-1] = int(nums[i-2] < nums[i-1] > nums[i]) 
            else:
                if i - 2 >= 0:
                    p[i-1] = int(nums[i-2] < nums[i-1] > nums[i]) 
                p[i] = int(nums[i-1] < nums[i] > nums[i+1])
                if i + 2 < n:
                    p[i+1] = int(nums[i] < nums[i+1] > nums[i+2]) 

        res = []
        for type_, a, b in queries:
            if type_ == 2:
                change(a, b)
                if a - 1 >= 0:
                    segment_tree.point_update(a-1, int(p[a-1]))
                segment_tree.point_update(a, int(p[a]))
                if a + 1 < n:
                    segment_tree.point_update(a+1, int(p[a+1]))
            else:
                res.append(segment_tree.range_query(a+1, b-1))
        return res

78000