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

---

前缀和数组是一个累加到特定索引的所有连续元素的总和的数组。它是一种广泛用于数组重构以改进时间复杂度的技术。树状数组，也称为二进制索引树 (BIT)，是一种数据结构，可以有效地更新元素并以对数时间复杂度计算前缀和。

在本文中，我们将讨论如何在 C++ 中使用树状数组更新从前缀和数组中找到给定值（称为 K）的下界。

语法

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

算法

要确定带有树状数组更新的前缀和数组中 K 的最小值，请遵循以下复杂步骤：

• 实例化一个大小为 n+1 的树状数组 (BIT)，并将所有元素初始化为 0。

• 使用 update() 函数使用给定的前缀和数组修改树状数组。

• 对树状数组执行查询以确定 K 的下界。从 n 的二进制表示中的最高位开始，并从该位迭代到最低位。使用 query() 函数检查当前前缀和是否小于或等于 K。如果满足此条件，则从 K 中减去当前前缀和并更新索引以移动到下一位。如果不满足，则移动到下一位而不更新索引。

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

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

方法

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

• 方法 2 - 使用延迟传播在树状数组上进行二分查找。

方法 1

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

示例

此代码的基本机制是使用树状数组，也称为二进制索引树。它的目的是确定前缀和数组中指定值（表示为“k”）的下界。这是通过使用 update 函数构造树状数组来完成的，该函数将前缀和数组中每个元素的值合并到树状数组中的相应位置。

然后，findLowerBound 函数使用二分查找算法通过使用 query 函数来精确定位前缀和数组中“k”的下界。此函数计算树状数组中直到当前索引的值的累积和。最终，代码以识别前缀和数组中“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

为了进一步优化树状数组，可以使用一种称为延迟传播的技术。这种方法需要推迟对树状数组的更新，直到它们真正需要，从而减少更新次数并提高查询过程的效率。

示例

该代码提供了一种解决方案，用于在给定前缀和数组中找到给定值 K 的下限。前缀和数组是一个数组，其中每个元素构成原始数组中直到该索引（包括该索引）的所有元素的总和。下限是前缀和数组中的第一个索引，其中直到该索引的所有元素的总和等于或超过 K。该解决方案使用树状数组数据结构和延迟传播技术来提高解决方案的效率。该代码包含用于修改树状数组、计算前缀和以及查找下限的函数。该代码还初始化前缀和数组、树状数组和延迟传播数组。最后，它输出前缀和数组中 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.

结论

本文讨论了如何在 C++ 编程领域中，使用巧妙的树状数组算法，从经过精心设计的包含更新的前缀和数组中找到值 K 的难以捉摸的阈值。深入探讨了两种高效方法：在树状数组上进行二分查找以及使用延迟传播在树状数组上进行二分查找。根据特定难题的具体需求和约束，仔细选择最合适的方法。希望这能阐明从包含更新的前缀和数组中查找 K 的下界的概念化和实现，利用树状数组在 C++ 领域中无与伦比的力量。