24. 树状数组1-白红宇

24. 树状数组1

阅读量：796 次

发布时间：2023-03-23

本文共 1572 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要处理一个长度为N的数列，并对它执行M次操作。操作有两种类型：一种是将某个位置的数加上一个值，另一种是求某个区间内所有数的和。为了高效处理这些操作，我们使用Fenwick树（Binary Indexed Tree）来实现。

方法思路

问题分析：

我们需要处理两种操作：点更新和区间和查询。

直接使用数组处理这些操作会导致效率低下，特别是在数据规模较大时。

Fenwick树能够在O(logN)时间内完成点更新和区间查询，非常适合这个问题。

Fenwick树的实现：

点更新：将一个位置的值加上一个增量。

区间和查询：计算从1到某个位置的前缀和，然后通过前缀和计算任意区间的和。

算法步骤：

初始化Fenwick树，将初始数组的值加入树中。

处理每个操作，点更新使用Fenwick树的更新函数，区间和查询使用前缀和函数计算。

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          using namespace std; class FenwickTree { private: vector
         
           tree; int size; public: FenwickTree(int s) : tree(s + 2), size(s) {} void update(int x, int delta) { while (x <= size) { tree[x] += delta; x += lowbit(x); } } int get_sum(int x) { int res = 0; while (x > 0) { res += tree[x]; x -= lowbit(x); } return res; } }; int lowbit(int t) { return t & (-t); } int main() { int n, m; scanf("%d %d", &n, &m); vector
          
            c(n + 2, 0); // 1-based indexing for (int i = 1; i <= n; ++i) { scanf("%d", &c[i]); } FenwickTree ft(n); for (int i = 1; i <= n; ++i) { ft.update(i, c[i]); } for (int i = 0; i < m; ++i) { int a, x, y; scanf("%d %d %d", &a, &x, &y); if (a == 1) { ft.update(x, y); } else { int sum_y = ft.get_sum(y); int sum_x_1 = ft.get_sum(x - 1); int res = sum_y - sum_x_1; cout << res << endl; } } return 0; }

代码解释

FenwickTree类：

初始化时，创建一个大小为N+2的向量tree。

update方法用于对某个位置进行点更新。

get_sum方法用于计算前缀和，用于区间和查询。

lowbit函数：

计算最低有效位，用于Fenwick树的内部操作。

主函数：

读取输入数据，初始化数组。

初始化Fenwick树，并将初始数组值加入树中。

处理每个操作，点更新使用update，区间和查询使用get_sum计算。

这种方法确保了每个操作的时间复杂度为O(logN)，能够高效处理大规模数据。

转载地址：http://iaqfk.baihongyu.com/

你可能感兴趣的文章