Индекс k-го установленного бита в двоичном массиве с запросами на обновление
Дан двоичный массив arr [] и q запросов следующих типов:
- k: найти индекс k- го установленного бита, т.е. k- го 1 в массиве.
- (x, y): обновить arr [x] = y, где y может быть 0 или 1 .
Примеры:
Input: arr[] = {1, 0, 1, 0, 0, 1, 1, 1}, q = 2
k = 4
(x, y) = (5, 1)
Output:
Index of 4th set bit: 6
Array after updation:
1 0 1 0 0 0 1 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: простое решение - запустить цикл от 0 до n - 1 и найти k th 1 . Чтобы обновить значение, просто выполните arr [i] = x . Первая операция занимает O (n) раз, а вторая операция занимает O (1) раз.
Другое решение - создать еще один массив и сохранить каждый индекс 1 в i- м индексе этого массива. Индекс K th 1 теперь может быть вычислен за время O (1), но операция обновления теперь занимает O (n) времени. Это хорошо работает, если количество операций запроса велико и очень мало обновлений.
Но что, если количество запросов и обновлений одинаково? Мы можем выполнить обе операции за время O (log n), используя дерево сегментов, чтобы выполнить обе операции за время O (logn) .
Representation of Segment tree:
- Leaf Nodes are the elements of the input array.
- Each internal node represents sum merging of the leaf nodes.
An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2*i+1, right child at 2*i+2 and the parent is at (i-1)/2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to build the tree void buildTree( int * tree, int * a, int s, int e, int idx) { // s = starting index // e = ending index // a = array storing binary string of numbers // idx = starting index = 1, for recurring the tree if (s == e) { // store each element value at the // leaf node tree[idx] = a[s]; return ; } int mid = (s + e) / 2; // Recurring in two sub portions (left, right) // to build the segment tree // Calling for the left sub portion buildTree(tree, a, s, mid, 2 * idx); // Calling for the right sub portion buildTree(tree, a, mid + 1, e, 2 * idx + 1); // Summing up the number of one"s tree[idx] = tree[2 * idx] + tree[2 * idx + 1]; return ; } // Function to return the index of the query int queryTree( int * tree, int s, int e, int k, int idx) { // s = starting index // e = ending index // k = searching for kth bit // idx = starting index = 1, for recurring the tree // k > number of 1"s in a binary string if (k > tree[idx]) return -1; // leaf node at which kth 1 is stored if (s == e) return s; int mid = (s + e) / 2; // If left sub-tree contains more or equal 1"s // than required kth 1 if (tree[2 * idx] >= k) return queryTree(tree, s, mid, k, 2 * idx); // If left sub-tree contains less 1"s than // required kth 1 then recur in the right sub-tree else return queryTree(tree, mid + 1, e, k - tree[2 * idx], 2 * idx + 1); } // Function to perform the update query void updateTree( int * tree, int s, int e, int i, int change, int idx) { // s = starting index // e = ending index // i = index at which change is to be done // change = new changed bit // idx = starting index = 1, for recurring the tree // Out of bounds request if (i < s || i > e) { cout << "error" ; return ; } // Leaf node of the required index i if (s == e) { // Replacing the node value with // the new changed value tree[idx] = change; return ; } int mid = (s + e) / 2; // If the index i lies in the left sub-tree if (i >= s && i <= mid) updateTree(tree, s, mid, i, change, 2 * idx); // If the index i lies in the right sub-tree else updateTree(tree, mid + 1, e, i, change, 2 * idx + 1); // Merging both left and right sub-trees tree[idx] = tree[2 * idx] + tree[2 * idx + 1]; return ; } // Function to perform queries void queries( int * tree, int * a, int q, int p, int k, int change, int n) { int s = 0, e = n - 1, idx = 1; if (q == 1) { // q = 1 update, p = index at which change // is to be done, change = new bit a[p] = change; updateTree(tree, s, e, p, change, idx); cout << "Array after updation:
" ; for ( int i = 0; i < n; i++) cout << a[i] << " " ; cout << "
" ; } else { // q = 0, print kth bit cout << "Index of " << k << "th set bit: " << queryTree(tree, s, e, k, idx) << "
" ; } } // Driver code int main() { int a[] = { 1, 0, 1, 0, 0, 1, 1, 1 }; int n = sizeof (a) / sizeof ( int ); // Declaring & initializing the tree with // maximum possible size of the segment tree // and each value initially as 0 int * tree = new int [4 * n + 1]; for ( int i = 0; i < 4 * n + 1; ++i) { tree[i] = 0; } // s and e are the starting and ending // indices respectively int s = 0, e = n - 1, idx = 1; // Build the segment tree buildTree(tree, a, s, e, idx); // Find index of kth set bit int q = 0, p = 0, change = 0, k = 4; queries(tree, a, q, p, k, change, n); // Update query q = 1, p = 5, change = 0; queries(tree, a, q, p, k, change, n); return 0; } |
Java
// Java implementation of the approach import java.io.*; import java.util.*; class GFG { // Function to build the tree static void buildTree( int [] tree, int [] a, int s, int e, int idx) { // s = starting index // e = ending index // a = array storing binary string of numbers // idx = starting index = 1, for recurring the tree if (s == e) { // store each element value at the // leaf node tree[idx] = a[s]; return ; } int mid = (s + e) / 2 ; // Recurring in two sub portions (left, right) // to build the segment tree // Calling for the left sub portion buildTree(tree, a, s, mid, 2 * idx); // Calling for the right sub portion buildTree(tree, a, mid + 1 , e, 2 * idx + 1 ); // Summing up the number of one"s tree[idx] = tree[ 2 * idx] + tree[ 2 * idx + 1 ]; return ; } // Function to return the index of the query static int queryTree( int [] tree, int s, int e, int k, int idx) { // s = starting index // e = ending index // k = searching for kth bit // idx = starting index = 1, for recurring the tree // k > number of 1"s in a binary string if (k > tree[idx]) return - 1 ; // leaf node at which kth 1 is stored if (s == e) return s; int mid = (s + e) / 2 ; // If left sub-tree contains more or equal 1"s // than required kth 1 if (tree[ 2 * idx] >= k) return queryTree(tree, s, mid, k, 2 * idx); // If left sub-tree contains less 1"s than // required kth 1 then recur in the right sub-tree else return queryTree(tree, mid + 1 , e, k - tree[ 2 * idx], 2 * idx + 1 ); } // Function to perform the update query static void updateTree( int [] tree, int s, int e, int i, int change, int idx) { // s = starting index // e = ending index // i = index at which change is to be done // change = new changed bit // idx = starting index = 1, for recurring the tree // Out of bounds request if (i < s || i > e) { System.out.println( "Error" ); return ; } // Leaf node of the required index i if (s == e) { // Replacing the node value with // the new changed value tree[idx] = change; return ; } int mid = (s + e) / 2 ; // If the index i lies in the left sub-tree if (i >= s && i <= mid) updateTree(tree, s, mid, i, change, 2 * idx); // If the index i lies in the right sub-tree else updateTree(tree, mid + 1 , e, i, change, 2 * idx + 1 ); // Merging both left and right sub-trees tree[idx] = tree[ 2 * idx] + tree[ 2 * idx + 1 ]; return ; } // Function to perform queries static void queries( int [] tree, int [] a, int q, int p, int k, int change, int n) { int s = 0 , e = n - 1 , idx = 1 ; if (q == 1 ) { // q = 1 update, p = index at which change // is to be done, change = new bit a[p] = change; updateTree(tree, s, e, p, change, idx); System.out.println( "Array after updation:" ); for ( int i = 0 ; i < n; i++) System.out.print(a[i] + " " ); System.out.println(); } else { // q = 0, print kth bit System.out.printf( "Index of %dth set bit: %d
" , k, queryTree(tree, s, e, k, idx)); } } // Driver Code public static void main(String[] args) { int [] a = { 1 , 0 , 1 , 0 , 0 , 1 , 1 , 1 }; int n = a.length; // Declaring & initializing the tree with // maximum possible size of the segment tree // and each value initially as 0 int [] tree = new int [ 4 * n + 1 ]; for ( int i = 0 ; i < 4 * n + 1 ; ++i) { tree[i] = 0 ; } // s and e are the starting and ending // indices respectively int s = 0 , e = n - 1 , idx = 1 ; // Build the segment tree buildTree(tree, a, s, e, idx); // Find index of kth set bit int q = 0 , p = 0 , change = 0 , k = 4 ; queries(tree, a, q, p, k, change, n); // Update query q = 1 ; p = 5 ; change = 0 ; queries(tree, a, q, p, k, change, n); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 implementation of the approach # Function to build the tree def buildTree(tree: list , a: list , s: int , e: int , idx: int ): РЕКОМЕНДУЕМЫЕ СТАТЬИ |