高新网站建设多少钱,酒店网站制作,郑州 服装 网站建设,全国建筑工程网解决的问题#xff1a; 维护一个长度为 n 的数组 arr#xff08;初始通常全为0#xff09;。 支持操作#xff1a; 单点更新#xff08;Update#xff09;#xff1a;将 arr[i] 的值增加#xff08;或修改为#xff09;delta#xff08;或 value#xff09;。 前缀… 解决的问题 维护一个长度为 n 的数组 arr初始通常全为0。 支持操作 单点更新Update将 arr[i] 的值增加或修改为delta或 value。 前缀查询Query快速查询 arr[1] arr[2] ... arr[i] 的和前缀和。 衍生操作 区间查询Range Query利用前缀和相减Query(r) - Query(l-1)计算 arr[l] ... arr[r] 的和。 单点查询Point Query结合差分思想构建差分数组的树状数组或直接用 Query(i) - Query(i-1)如果支持单点查询。 区间更新Range Update结合差分思想构建差分数组的树状数组支持 arr[l..r] 每个元素增加 delta。 求逆序对Inversion Count离散化 树状数组统计。 应用场景总结 动态单点修改 区间和查询 最直接的应用。 动态逆序对计数 离散化原始数据然后从左到右或从右到左扫描利用树状数组查询已扫描元素中比当前元素大或小的元素个数即新增的逆序对数。 动态区间更新 单点查询 利用差分思想。令 diff[i] arr[i] - arr[i-1]arr[0]0构建 diff 数组的树状数组。 区间更新 [l, r] deltaupdate(l, delta); update(r1, -delta); 单点查询 arr[i]query(i) (等于 diff[1]...diff[i]即 arr[i]) 动态区间更新 区间和查询 需要两个树状数组维护差分数组 diff[i] 和 i * diff[i]推导稍复杂。 求第 K 小/大元素权值树状数组 配合离散化将元素值作为下标在树状数组中进行计数。通过二分查找前缀和 k 的最小位置。 核心思想 分块存储前缀和信息 不是直接存储原始数组 arr也不是存储所有前缀和而是存储一个辅助数组 tree。 利用二进制表示 tree 数组的索引 i 的二进制表示决定了它存储哪些 arr 元素的和。具体来说 tree[i] arr[j] arr[j1] ... arr[i]其中 j i - lowbit(i) 1。 Lowbit 函数 这是树状数组的灵魂。lowbit(i) 表示数字 i 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。计算公式 lowbit(i) i (-i) 利用补码特性 结构特点 数组下标通常从 1 开始arr[1..n], tree[1..n]。下标 0 不使用。 tree[i] 负责的区间长度等于 lowbit(i)。 tree[i] 的父节点是 tree[i lowbit(i)]。 tree[i] 的子节点包括 tree[i - 2^k]其中 2^k lowbit(i)且 k 从 0 开始递增直到 i - 2^k i - lowbit(i)。这些节点构成了 tree[i] 覆盖范围的一部分。
优势与局限 优势 代码极其简洁核心函数通常只需几行。 效率高O(log n)常数因子小。 内存占用小O(n)。 局限 主要解决前缀和相关问题和、计数。虽然可以通过技巧实现区间更新、最值效率较低且复杂等但不如线段树直观和通用。 无法高效处理任意区间上的非和操作如区间最大值/最小值、区间乘积、复杂的区间合并信息。 下标通常需要从 1 开始。 模板:
lowbit:
lowbit(i) 表示数字 i 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。
计算公式 lowbit(i) i -i; 计算原理 -i 是 i 的补码按位取反后加 1 i -i 会保留 i 的最低位 1其余位变为 0
为什么 lowbit(i) 如此重要 高效性 更新和查询操作只需 O(log n) 时间 每次操作最多访问 log₂(n) 个节点 内存效率 仅需 O(n) 额外空间 比线段树更紧凑线段树需要 4n 空间 操作对称性 更新操作i lowbit(i)向上 查询操作i - lowbit(i)向左 定义数据结构本质 决定了每个节点存储的区间范围 建立了节点间的层级关系
核心代码
int n, m; // n为数组长度m为操作次数
int a[500005]; // 树状数组存储结构// 计算x的最低位1对应的数值lowbit操作
// 例如x6(110)-x1010x(-x)10(2)
int lowbit(int x) {return x (-x);
}// 向树状数组的第i个位置添加值w单点更新操作
// 时间复杂度O(log n)
void add(int i, int w) {/* 递归实现if (i n) {a[i] w;add(i lowbit(i), w);}*/// 迭代实现while (i n) {a[i] w; // 更新当前节点i lowbit(i); // 向上更新父节点跳转到下一个覆盖当前位置的节点}
}// 计算从1到i的前缀和区间查询操作
// 时间复杂度O(log n)
int count(int i) {/* 递归实现if (i 0) {return 0;}return count(i - lowbit(i)) a[i];*/// 迭代实现int result 0;while (i 0) {result a[i]; // 累加当前节点的值i - lowbit(i); // 向下查询子节点跳转到上一个不覆盖当前位置的节点}return result;
}
例题
树状数组 1 #define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includebits/stdc.h
using namespace std;
int n, m;
int a[500005];
int lowbit(int x) {return x (-x);
}
void add(int i, int w) {/*if (i n) {a[i] w;add(i lowbit(i), w);}*///或while (i n) {a[i] w;i lowbit(i);}
}
int count(int i) {/*if (i 0) {return 0;}return count(i - lowbit(i)) a[i];*///或int result 0;while (i 0) {result a[i];i - lowbit(i);}return result;
}
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin与cout绑定cin n m;int w;for (int i 1; i n; i) {cin w;add(i, w);}int h, x, k;for (int i 1; i m; i) {cin h x k;if (h 1) {add(x, k);}else {cout count(k) - count(x-1) endl;}}return 0;
}
