使用树状数组的前缀和数组更新，查询K的下界

首要序列总和数组是一个集合，它累积交错元素的总和，直到达到特定的索引。这是一种广泛应用于组合重构以优化时间复杂度的策略。树状数组，也被称为二进制索引树（BIT），是一种高效地更新元素并在对数时间复杂度内计算前序列总和的数据库形式。

在本文中，我们将讨论如何使用C++中的Fenwick Tree进行现代化改进，以从一个系列求和数组中揭示给定值的较小极限边界，这个值被称为K。

语法

语法定义了两个函数，update和query，以及一个用于Fenwick树的主函数，Fenwick树是一种用于高效范围查询和更新操作的数据结构。update函数接受一个索引idx，一个值val，数组的大小n，以及Fenwick树数组BIT。它通过将val添加到索引idx及其所有祖先的节点来更新Fenwick树。query函数接受一个索引idx和Fenwick树数组BIT。它返回从根节点到索引idx的节点的累积和。主函数声明数组的大小n，前缀和数组arr，以及初始化为0的Fenwick树数组BIT。

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;
}

算法

要确定带有Fenwick树更新的前缀和数组中K的最小值，请按照以下复杂的步骤进行 -

• 实例化大小为 n+1 的 Fenwick 树 (BIT)，将所有元素初始化为 0。

• 使用 update() 函数修改具有给定前缀和数组的 Fenwick Tree。

• 在Fenwick树上执行查询以确定K的下界。从n的二进制表示中的最高有效位开始迭代，直到最低有效位。使用query()函数验证当前前缀和是否小于或等于K。如果满足此条件，将当前前缀和从K中减去，并更新索引以移动到下一个位。如果不满足条件，则在不更新索引的情况下移动到下一个位。

• 遍历完所有位后，索引将表示前缀和数组中 K 的下界。

• 输出得到的索引作为K的下界。

方法

• 方法1 − 在Fenwick树上进行二分查找。在这种方法中，我们在Fenwick树上执行二分查找以找到K的下界。

• 方法2 - 在Fenwick树上进行带有延迟传播的二分查找。

方法 1

为了解决这个问题，我们首先将左指针和右指针分别设置为1和n（表示前缀和数组的大小），然后采用二分查找策略来确定对应于小于或等于K的最大前缀和的索引i。然后，根据前缀和[i]的值是否小于或等于K，更新左指针或右指针的位置。

示例

这段代码的基本机制是利用了一种叫做 Fenwick Tree（也称为 Binary Indexed Tree）的数据结构。它的作用是在前缀和数组中确定指定值 'k' 的下界。这是通过使用更新函数构建 Fenwick Tree 来实现的，该函数将前缀和数组中每个元素的值合并到 Fenwick Tree 的相应位置中。

findLowerBound 函数然后采用二分搜索算法，通过查询函数来查明前缀和数组中“k”的下界。此函数计算直至 Fenwick 树中当前索引的值的累积和。最终，代码最终识别出前缀和数组中“k”下界的索引，并将结果显示到控制台。

#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;
}

输出

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

方法2

为了进一步优化 Fenwick 树，可以采用一种称为惰性传播的技术。这种方法需要将对 Fenwick Tree 的更新推迟到实际需要时，从而减少更新次数并提高查询过程的效率。

示例

代码提供了一种解决方案，用于在前缀和数组中定位给定值K的下限。前缀和数组是一个数组，其中每个元素都是原始数组中从索引0到该索引的元素的总和。下限是前缀和数组中第一个使得到该索引的元素之和等于或超过K的索引。该解决方案使用Fenwick树数据结构和延迟传播技术来增强解决方案的效率。代码包括修改Fenwick树、计算前缀和和查找下限的函数。代码还初始化了前缀和数组、Fenwick树和延迟传播数组。最后，它输出了前缀和数组中K的下限。

#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;
}

输出

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.

结论

关于从精心设计的前缀和数组中挖掘难以捉摸的 K 值阈值的讨论，并通过更新进行强化，利用 C++ 编程领域中巧妙的芬威克树算法。深入研究两种高效方法的复杂性：Fenwick 树上的二分搜索和带有惰性传播的 Fenwick 树上的二分搜索。根据您的特定难题的具体要求和限制，仔细选择最合适的方法。希望这能够阐明这一难以捉摸的任务的概念化和实现，即利用 C++ 领域中 Fenwick 树无与伦比的功能，从带有更新的前缀和数组中找到 K 的下界。

以上是使用树状数组的前缀和数组更新，查询K的下界的详细内容。更多信息请关注PHP中文网其他相关文章！