树状数组简单易懂的详解

//树形数组

//树形数组是一种

，可以用来高效地维护数组的前缀和，支持单点修改和区间查询

//树形数组的操作时间复杂度为O(logN)，比线性的暴力

要快很多

#include <iostream>

#include <vector>

using namespace std;

//树形数组的实现

class FenwickTree {

public:

FenwickTree(int n) {

tree.resize(n + 1); //树形数组的大小为n+1

}

//单点修改，将i位置上的值加上val

void update(int i, int val) {

while (i < tree.size()) {

tree[i] += val; //更新树形数组的值

i += lowbit(i); //更新i的值

}

}

//区间查询，查询区间[1, i]上的和

int query(int i) {

int sum = 0;

while (i > 0) {

sum += tree[i]; //累加区间[1, i]上的和

i -= lowbit(i); //更新i的值

}

return sum;

}

private:

vector<int> tree; //树形数组

//lowbit函数用于计算一个数的二进制表示中的最低位1所代表的值

int lowbit(int x) {

return x & -x;

}

};

int main() {

int n;

cin >> n;

FenwickTree tree(n); //创建一个大小为n的树形数组

for (int i = 1; i <= n; i++) {

int x;

cin >> x;

tree.update(i, x); //将第i个位置上的值设置为x

}

int q;

cin >> q;

while (q--) {

int op, x, y;

cin >> op >> x >> y;

if (op == 1) {

tree.update(x, y); //将第x个位置上的值加上y

} else {

cout << tree.query(y) - tree.query(x - 1) << endl; //查询区间[x, y]上的和

}

}

return 0;

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/2193.html