Binary Indexed Tree
Segment Tree
Array
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:
queries[i] = [1, li , ri ]
, determine the count of peak elements in the subarray nums[li ..ri ]
.
queries[i] = [2, indexi , vali ]
, change nums[indexi ]
to vali
.
Return an array answer
containing the results of the queries of the first type in order.
Notes:
The first and the last element of an array or a subarray cannot be a peak.
Example 1:
Input: nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]
Output: [0]
Explanation:
First query: We change nums[3]
to 4 and nums
becomes [3,1,4,4,5]
.
Second query: The number of peaks in the [3,1,4,4,5]
is 0.
Example 2:
Input: nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]
Output: [0,1]
Explanation:
First query: nums[2]
should become 4, but it is already set to 4.
Second query: The number of peaks in the [4,1,4]
is 0.
Third query: The second 4 is a peak in the [4,1,4,2,1]
.
Constraints:
3 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i][0] == 1
or queries[i][0] == 2
For all i
that:
queries[i][0] == 1
: 0 <= queries[i][1] <= queries[i][2] <= nums.length - 1
queries[i][0] == 2
: 0 <= queries[i][1] <= nums.length - 1
, 1 <= queries[i][2] <= 105
Solutions
Solution 1: Binary Indexed Tree
According to the problem description, for $0 < i < n - 1$, if it satisfies $nums[i - 1] < nums[i]$ and $nums[i] > nums[i + 1]$, we can consider $nums[i]$ as $1$, otherwise as $0$. Thus, for operation $1$, i.e., querying the number of peak elements in the subarray $nums[l..r]$, it is equivalent to querying the number of $1$s in the interval $[l + 1, r - 1]$. We can use a binary indexed tree to maintain the number of $1$s in the interval $[1, n - 1]$.
For operation $1$, i.e., updating $nums[idx]$ to $val$, it will only affect the values at positions $idx - 1$, $idx$, and $idx + 1$, so we only need to update these three positions. Specifically, we can first remove the peak elements at these three positions, then update the value of $nums[idx]$, and finally add back the peak elements at these three positions.
The time complexity is $O((n + q) \times \log n)$, and the space complexity is $O(n)$. Here, $n$ and $q$ are the lengths of the array nums
and the query array queries
, respectively.
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 class BinaryIndexedTree :
__slots__ = "n" , "c"
def __init__ ( self , n : int ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
def update ( self , x : int , delta : int ) -> None :
while x <= self . n :
self . c [ x ] += delta
x += x & - x
def query ( self , x : int ) -> int :
s = 0
while x :
s += self . c [ x ]
x -= x & - x
return s
class Solution :
def countOfPeaks ( self , nums : List [ int ], queries : List [ List [ int ]]) -> List [ int ]:
def update ( i : int , val : int ):
if i <= 0 or i >= n - 1 :
return
if nums [ i - 1 ] < nums [ i ] and nums [ i ] > nums [ i + 1 ]:
tree . update ( i , val )
n = len ( nums )
tree = BinaryIndexedTree ( n - 1 )
for i in range ( 1 , n - 1 ):
update ( i , 1 )
ans = []
for q in queries :
if q [ 0 ] == 1 :
l , r = q [ 1 ] + 1 , q [ 2 ] - 1
ans . append ( 0 if l > r else tree . query ( r ) - tree . query ( l - 1 ))
else :
idx , val = q [ 1 :]
for i in range ( idx - 1 , idx + 2 ):
update ( i , - 1 )
nums [ idx ] = val
for i in range ( idx - 1 , idx + 2 ):
update ( i , 1 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
this . c = new int [ n + 1 ] ;
}
public void update ( int x , int delta ) {
for (; x <= n ; x += x & - x ) {
c [ x ] += delta ;
}
}
public int query ( int x ) {
int s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += c [ x ] ;
}
return s ;
}
}
class Solution {
private BinaryIndexedTree tree ;
private int [] nums ;
public List < Integer > countOfPeaks ( int [] nums , int [][] queries ) {
int n = nums . length ;
this . nums = nums ;
tree = new BinaryIndexedTree ( n - 1 );
for ( int i = 1 ; i < n - 1 ; ++ i ) {
update ( i , 1 );
}
List < Integer > ans = new ArrayList <> ();
for ( var q : queries ) {
if ( q [ 0 ] == 1 ) {
int l = q [ 1 ] + 1 , r = q [ 2 ] - 1 ;
ans . add ( l > r ? 0 : tree . query ( r ) - tree . query ( l - 1 ));
} else {
int idx = q [ 1 ] , val = q [ 2 ] ;
for ( int i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , - 1 );
}
nums [ idx ] = val ;
for ( int i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , 1 );
}
}
}
return ans ;
}
private void update ( int i , int val ) {
if ( i <= 0 || i >= nums . length - 1 ) {
return ;
}
if ( nums [ i - 1 ] < nums [ i ] && nums [ i ] > nums [ i + 1 ] ) {
tree . update ( i , val );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 class BinaryIndexedTree {
private :
int n ;
vector < int > c ;
public :
BinaryIndexedTree ( int n )
: n ( n )
, c ( n + 1 ) {}
void update ( int x , int delta ) {
for (; x <= n ; x += x & - x ) {
c [ x ] += delta ;
}
}
int query ( int x ) {
int s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += c [ x ];
}
return s ;
}
};
class Solution {
public :
vector < int > countOfPeaks ( vector < int >& nums , vector < vector < int >>& queries ) {
int n = nums . size ();
BinaryIndexedTree tree ( n - 1 );
auto update = [ & ]( int i , int val ) {
if ( i <= 0 || i >= n - 1 ) {
return ;
}
if ( nums [ i - 1 ] < nums [ i ] && nums [ i ] > nums [ i + 1 ]) {
tree . update ( i , val );
}
};
for ( int i = 1 ; i < n - 1 ; ++ i ) {
update ( i , 1 );
}
vector < int > ans ;
for ( auto & q : queries ) {
if ( q [ 0 ] == 1 ) {
int l = q [ 1 ] + 1 , r = q [ 2 ] - 1 ;
ans . push_back ( l > r ? 0 : tree . query ( r ) - tree . query ( l - 1 ));
} else {
int idx = q [ 1 ], val = q [ 2 ];
for ( int i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , -1 );
}
nums [ idx ] = val ;
for ( int i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , 1 );
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 type BinaryIndexedTree struct {
n int
c [] int
}
func NewBinaryIndexedTree ( n int ) * BinaryIndexedTree {
return & BinaryIndexedTree { n : n , c : make ([] int , n + 1 )}
}
func ( bit * BinaryIndexedTree ) update ( x , delta int ) {
for ; x <= bit . n ; x += x & - x {
bit . c [ x ] += delta
}
}
func ( bit * BinaryIndexedTree ) query ( x int ) int {
s := 0
for ; x > 0 ; x -= x & - x {
s += bit . c [ x ]
}
return s
}
func countOfPeaks ( nums [] int , queries [][] int ) ( ans [] int ) {
n := len ( nums )
tree := NewBinaryIndexedTree ( n - 1 )
update := func ( i , val int ) {
if i <= 0 || i >= n - 1 {
return
}
if nums [ i - 1 ] < nums [ i ] && nums [ i ] > nums [ i + 1 ] {
tree . update ( i , val )
}
}
for i := 1 ; i < n - 1 ; i ++ {
update ( i , 1 )
}
for _ , q := range queries {
if q [ 0 ] == 1 {
l , r := q [ 1 ] + 1 , q [ 2 ] - 1
t := 0
if l <= r {
t = tree . query ( r ) - tree . query ( l - 1 )
}
ans = append ( ans , t )
} else {
idx , val := q [ 1 ], q [ 2 ]
for i := idx - 1 ; i <= idx + 1 ; i ++ {
update ( i , - 1 )
}
nums [ idx ] = val
for i := idx - 1 ; i <= idx + 1 ; i ++ {
update ( i , 1 )
}
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 class BinaryIndexedTree {
private n : number ;
private c : number [];
constructor ( n : number ) {
this . n = n ;
this . c = Array ( n + 1 ). fill ( 0 );
}
update ( x : number , delta : number ) : void {
for (; x <= this . n ; x += x & - x ) {
this . c [ x ] += delta ;
}
}
query ( x : number ) : number {
let s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += this . c [ x ];
}
return s ;
}
}
function countOfPeaks ( nums : number [], queries : number [][]) : number [] {
const n = nums . length ;
const tree = new BinaryIndexedTree ( n - 1 );
const update = ( i : number , val : number ) : void => {
if ( i <= 0 || i >= n - 1 ) {
return ;
}
if ( nums [ i - 1 ] < nums [ i ] && nums [ i ] > nums [ i + 1 ]) {
tree . update ( i , val );
}
};
for ( let i = 1 ; i < n - 1 ; ++ i ) {
update ( i , 1 );
}
const ans : number [] = [];
for ( const q of queries ) {
if ( q [ 0 ] === 1 ) {
const [ l , r ] = [ q [ 1 ] + 1 , q [ 2 ] - 1 ];
ans . push ( l > r ? 0 : tree.query ( r ) - tree . query ( l - 1 ));
} else {
const [ idx , val ] = [ q [ 1 ], q [ 2 ]];
for ( let i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , - 1 );
}
nums [ idx ] = val ;
for ( let i = idx - 1 ; i <= idx + 1 ; ++ i ) {
update ( i , 1 );
}
}
}
return ans ;
}
GitHub