Query the lower bound of K using the prefix and array update of the tree array

A primary sequence sum array is a collection that accumulates the sum of interleaved elements until a specific index is reached. This is a strategy widely used in combinatorial refactoring to optimize time complexity. Tree arrays, also known as Binary Index Trees (BITs), are a database form that efficiently updates elements and computes the sum of previous sequences in logarithmic time complexity.

In this article, we will discuss how to use a modern improvement of Fenwick Tree in C to reveal the smaller limit bound of a given value, called K, from a series summed array.

grammar

The syntax defines two functions, update and query, and a main function for the Fenwick tree, a data structure used for efficient range query and update operations. The update function accepts an index idx, a value val, the size of the array n, and the Fenwick tree array BIT. It updates the Fenwick tree by adding val to the node at index idx and all its ancestors. The query function accepts an index idx and Fenwick tree array BIT. It returns the cumulative sum from the root node to the node with index idx. The main function declares the size n of the array, the prefix and array arr, and the Fenwick tree array BIT initialized to 0.

void update(int idx, int val, int n, int BIT[]) {
   while (idx <= n) {
      BIT[idx] += val;
      idx += (idx & -idx);
   }
}
int query(int idx, int BIT[]) {
   int sum = 0;
   while (idx > 0) {
      sum += BIT[idx];
      idx -= (idx & -idx);
   }
   return sum;
}
// Driver code
int main() {
   int n; 
   int arr[n+1];
   int BIT[n+1] = {0}; 
   return 0;
}

algorithm

To determine the minimum value of K in the prefix and array with Fenwick tree update, follow the following complex steps -

• Instantiate a Fenwick tree (BIT) of size n 1, initializing all elements to 0.

• Use the update() function to modify the Fenwick Tree with the given prefix and array.

• Perform a query on the Fenwick tree to determine the lower bound of K. Iterate starting from the most significant bit in the binary representation of n to the least significant bit. Use the query() function to verify whether the current prefix sum is less than or equal to K. If this condition is met, the current prefix sum is subtracted from K and the index is updated to move to the next bit. If the condition is not met, move to the next bit without updating the index.

• After all bits have been traversed, the index will represent the prefix and the lower bound of K in the array.

• Output the obtained index as the lower bound of K.

method

• Method 1 − Perform binary search on Fenwick tree. In this method, we perform a binary search on the Fenwick tree to find the lower bound of K.

• Method 2 - Binary search with delayed propagation on Fenwick tree.

method 1

To solve this problem, we first set the left and right pointers to 1 and n respectively (indicating the size of the prefix and array), and then use a binary search strategy to determine the index corresponding to the largest prefix sum less than or equal to K i. Then, depending on whether the value of prefix sum [i] is less than or equal to K, the position of the left pointer or the right pointer is updated.

Example

The basic mechanism of this code is to utilize a data structure called Fenwick Tree (also known as Binary Indexed Tree). Its purpose is to determine the lower bound of the specified value 'k' in the prefix sum array. This is accomplished by constructing a Fenwick Tree using an update function that merges the prefix and value of each element in the array into the corresponding position in the Fenwick Tree.

The findLowerBound function then uses a binary search algorithm to find the lower bound of "k" in the prefix and array by querying the function. This function calculates the cumulative sum of values ​​up to the current index in the Fenwick tree. Eventually, the code ends up identifying the prefix and the index of the lower bound of "k" in the array, and displays the result to the console.

#include <iostream>
using namespace std;
void update(int i, int v, int n, int b[]) {
    while (i <= n) {
        b[i] += v;
        i += (i & -i);
    }
}
int query(int i, int b[]) {
    int s = 0;
    while (i > 0) {
        s += b[i];
        i -= (i & -i);
    }
    return s;
}
int findLowerBound(int k, int n, int p[], int b[]) {
    int l = 1, r = n, idx = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        int msum = query(m, b);
        if (msum <= k) {
            idx = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return idx;
}
int main() {
    int n = 5;
    int p[] = {0, 1, 3, 6, 10, 15};
    int b[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        update(i, p[i], n, b);
    }
    int k = 10, idx;
    idx = findLowerBound(k, n, p, b);
    cout << "The lower bound of " << k << " is at index " << idx << " in the prefix sum array." << endl;
    return 0;
}

Output

The lower bound of 10 is at index 3 in the prefix sum array.

Method 2

To further optimize Fenwick trees, a technique called lazy propagation can be used. This approach entails deferring updates to the Fenwick Tree until they are actually needed, thereby reducing the number of updates and making the query process more efficient.

Example

The code provides a solution for locating the lower bound of a given value K in a prefix sum array. A prefix sum array is an array where each element is the sum of the elements from index 0 to that index in the original array. The lower bound is the first index in the prefix sum array such that the sum of the elements up to that index equals or exceeds K. The solution uses Fenwick tree data structure and delay propagation technique to enhance the efficiency of the solution. The code includes functions for modifying Fenwick trees, calculating prefix sums, and finding lower bounds. The code also initializes prefix sum arrays, Fenwick trees, and delayed propagation arrays. Finally, it outputs the prefix and the lower bound of K in the array.

#include  <iostream>
#include  <cstring>
using namespace std;

void update(int idx, int val, int n, int ft[], int lz[]) {
   while (idx  <= n) ft[idx] += val, idx += (idx & -idx);
}

int getPrefixSum(int idx, int ft[]) {
   int sum = 0;
   while (idx > 0) sum += ft[idx], idx -= (idx & -idx);
   return sum;
}

int findLowerBound(int K, int n, int ps[], int ft[], int lz[]) {
   int l = 1, r = n, lb = 0;
   while (l  <= r) {
      int m = (l + r) / 2, s = getPrefixSum(m, ft) + lz[m];
      if (s  <= K) lb = m, l = m + 1;
      else r = m - 1;
   }
   return lb;
}

int main() {
   int n = 5;
   int ps[] = {0, 1, 3, 6, 10, 15};
   int ft[n + 1], lz[n + 1]; memset(ft, 0, sizeof(ft)); memset(lz, 0, sizeof(lz));
   for (int i = 1; i  <= n; i++) update(i, ps[i] - ps[i - 1], n, ft, lz);
   int K = 10;
   int lb = findLowerBound(K, n, ps, ft, lz);
   cout << "For the given array with size " << n << " and prefix sum array [";
   for (int i = 1; i <= n; i++) {
      cout << ps[i];
      if (i < n) cout << ", ";
   }
   cout << "], the lower bound of " << K << " is at index " << lb << " in the prefix sum array." << endl;
   return 0;
}

Output

For the given array with size 5 and prefix sum array [1, 3, 6, 10, 15], the lower bound of 10 is at index 4 in the prefix sum array.

in conclusion

A discussion on mining elusive K-value thresholds from carefully designed prefixes and arrays, enhanced by an update that takes advantage of the clever Fenwick tree algorithm from the world of C programming. Dive into the complexities of two efficient methods: binary search on Fenwick trees and binary search on Fenwick trees with lazy propagation. Carefully choose the most appropriate method based on the specific requirements and constraints of your particular problem. Hopefully this sheds light on the conceptualization and implementation of the elusive task of finding a lower bound on K from an array of prefix sums with updates, leveraging the unparalleled power of Fenwick trees in the C domain.

The above is the detailed content of Query the lower bound of K using the prefix and array update of the tree array. For more information, please follow other related articles on the PHP Chinese website!