Binary Indexed Tree
Array
Simulation
Description
Given the array queries
of positive integers between 1
and m
, you have to process all queries[i]
(from i=0
to i=queries.length-1
) according to the following rules:
In the beginning, you have the permutation P=[1,2,3,...,m]
.
For the current i
, find the position of queries[i]
in the permutation P
(indexing from 0 ) and then move this at the beginning of the permutation P
. Notice that the position of queries[i]
in P
is the result for queries[i]
.
Return an array containing the result for the given queries
.
Example 1:
Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1]
Explanation: The queries are processed as follow:
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2 , then we move 3 to the beginning of P resulting in P=[3,1,2,4,5].
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1 , then we move 1 to the beginning of P resulting in P=[1,3,2,4,5].
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2 , then we move 2 to the beginning of P resulting in P=[2,1,3,4,5].
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1 , then we move 1 to the beginning of P resulting in P=[1,2,3,4,5].
Therefore, the array containing the result is [2,1,2,1].
Example 2:
Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]
Example 3:
Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]
Constraints:
1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def processQueries ( self , queries : List [ int ], m : int ) -> List [ int ]:
p = list ( range ( 1 , m + 1 ))
ans = []
for v in queries :
j = p . index ( v )
ans . append ( j )
p . pop ( j )
p . insert ( 0 , v )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public int [] processQueries ( int [] queries , int m ) {
List < Integer > p = new LinkedList <> ();
for ( int i = 1 ; i <= m ; ++ i ) {
p . add ( i );
}
int [] ans = new int [ queries . length ] ;
int i = 0 ;
for ( int v : queries ) {
int j = p . indexOf ( v );
ans [ i ++] = j ;
p . remove ( j );
p . add ( 0 , v );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
vector < int > processQueries ( vector < int >& queries , int m ) {
vector < int > p ( m );
iota ( p . begin (), p . end (), 1 );
vector < int > ans ;
for ( int v : queries ) {
int j = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
if ( p [ i ] == v ) {
j = i ;
break ;
}
}
ans . push_back ( j );
p . erase ( p . begin () + j );
p . insert ( p . begin (), v );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func processQueries ( queries [] int , m int ) [] int {
p := make ([] int , m )
for i := range p {
p [ i ] = i + 1
}
ans := [] int {}
for _ , v := range queries {
j := 0
for i := range p {
if p [ i ] == v {
j = i
break
}
}
ans = append ( ans , j )
p = append ( p [: j ], p [ j + 1 :] ... )
p = append ([] int { v }, p ... )
}
return ans
}
Solution 2
Python3 Java C++ Go
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 class BinaryIndexedTree :
def __init__ ( self , n ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
@staticmethod
def lowbit ( x ):
return x & - x
def update ( self , x , delta ):
while x <= self . n :
self . c [ x ] += delta
x += BinaryIndexedTree . lowbit ( x )
def query ( self , x ):
s = 0
while x > 0 :
s += self . c [ x ]
x -= BinaryIndexedTree . lowbit ( x )
return s
class Solution :
def processQueries ( self , queries : List [ int ], m : int ) -> List [ int ]:
n = len ( queries )
pos = [ 0 ] * ( m + 1 )
tree = BinaryIndexedTree ( m + n )
for i in range ( 1 , m + 1 ):
pos [ i ] = n + i
tree . update ( n + i , 1 )
ans = []
for i , v in enumerate ( queries ):
j = pos [ v ]
tree . update ( j , - 1 )
ans . append ( tree . query ( j ))
pos [ v ] = n - i
tree . update ( n - 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 class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
c = new int [ n + 1 ] ;
}
public void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
public int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ] ;
x -= lowbit ( x );
}
return s ;
}
public static int lowbit ( int x ) {
return x & - x ;
}
}
class Solution {
public int [] processQueries ( int [] queries , int m ) {
int n = queries . length ;
BinaryIndexedTree tree = new BinaryIndexedTree ( m + n );
int [] pos = new int [ m + 1 ] ;
for ( int i = 1 ; i <= m ; ++ i ) {
pos [ i ] = n + i ;
tree . update ( n + i , 1 );
}
int [] ans = new int [ n ] ;
int k = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = queries [ i ] ;
int j = pos [ v ] ;
tree . update ( j , - 1 );
ans [ k ++] = tree . query ( j );
pos [ v ] = n - i ;
tree . update ( n - 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 class BinaryIndexedTree {
public :
int n ;
vector < int > c ;
BinaryIndexedTree ( int _n )
: n ( _n )
, c ( _n + 1 ) {}
void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ];
x -= lowbit ( x );
}
return s ;
}
int lowbit ( int x ) {
return x & - x ;
}
};
class Solution {
public :
vector < int > processQueries ( vector < int >& queries , int m ) {
int n = queries . size ();
vector < int > pos ( m + 1 );
BinaryIndexedTree * tree = new BinaryIndexedTree ( m + n );
for ( int i = 1 ; i <= m ; ++ i ) {
pos [ i ] = n + i ;
tree -> update ( n + i , 1 );
}
vector < int > ans ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = queries [ i ];
int j = pos [ v ];
tree -> update ( j , -1 );
ans . push_back ( tree -> query ( j ));
pos [ v ] = n - i ;
tree -> update ( n - 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 type BinaryIndexedTree struct {
n int
c [] int
}
func newBinaryIndexedTree ( n int ) * BinaryIndexedTree {
c := make ([] int , n + 1 )
return & BinaryIndexedTree { n , c }
}
func ( this * BinaryIndexedTree ) lowbit ( x int ) int {
return x & - x
}
func ( this * BinaryIndexedTree ) update ( x , delta int ) {
for x <= this . n {
this . c [ x ] += delta
x += this . lowbit ( x )
}
}
func ( this * BinaryIndexedTree ) query ( x int ) int {
s := 0
for x > 0 {
s += this . c [ x ]
x -= this . lowbit ( x )
}
return s
}
func processQueries ( queries [] int , m int ) [] int {
n := len ( queries )
pos := make ([] int , m + 1 )
tree := newBinaryIndexedTree ( m + n )
for i := 1 ; i <= m ; i ++ {
pos [ i ] = n + i
tree . update ( n + i , 1 )
}
ans := [] int {}
for i , v := range queries {
j := pos [ v ]
tree . update ( j , - 1 )
ans = append ( ans , tree . query ( j ))
pos [ v ] = n - i
tree . update ( n - i , 1 )
}
return ans
}
GitHub