算法基础--Fenwick树的实现原理

线段树与Fenwick树详解及C语言实现 线段树简介

线段树（Segment Tree）是一种二叉树结构，主要用于在数组修改的同时，快速进行区间查询。常见应用包括区间求和、区间最小值、区间最大值等。

线段树的特点 时间复杂度：构建、查询和更新均为O(log n)适用场景：频繁的区间操作，如区间更新和查询

---

Fenwick树（树状数组）简介

Fenwick树（树状数组）是一种高效处理前缀和及单点更新的数据结构。其核心操作是通过lowbit函数获取当前索引的最低位1所代表的值。

Fenwick树的特点 时间复杂度：构建、查询和更新均为O(log n)适用场景：前缀和查询和单点更新 Fenwick树的C语言实现 #include <stdio.h> #define MAXN 1000 int tree[MAXN + 1]; int lowbit(int x) { return x & -x; } void update(int index, int value, int n) { while (index <= n) { tree[index] += value; index += lowbit(index); } } int query(int index) { int result = 0; while (index > 0) { result += tree[index]; index -= lowbit(index); } return result; } int range_query(int left, int right) { return query(right) - query(left - 1); } int main() { int n = 10, arr[] = {0, 1, 7, 3, 0, 7, 8, 3, 2, 6, 2}; for (int i = 1; i <= n; i++) update(i, arr[i], n); printf("前5个元素的和：%d\n", query(5)); printf("区间[3, 7]的元素和：%d\n", range_query(3, 7)); update(4, 5, n); printf("更新后前5个元素的和：%d\n", query(5)); return 0; }

---

Fenwick树的下标示意图

以下为大小为25的Fenwick树的下标关系示意图： 在这里插入图片描述

graph TD A1[1] --> A2[2] A2 --> A4[4] A3[3] --> A4 A4 --> A8[8] A5[5] --> A6[6] A6 --> A8 A7[7] --> A8 A9[9] --> A10[10] A10 --> A12[12] A11[11] --> A12 A12 --> A16[16] A13[13] --> A14[14] A14 --> A16 A15[15] --> A16 A17[17] --> A18[18] A18 --> A20[20] A19[19] --> A20 A20 --> A24[24] A21[21] --> A22[22] A22 --> A24 A23[23] --> A24 A25[25] style A26 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 style A28 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 style A29 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 style A30 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 style A31 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 style A32 fill:#f0f0f0,stroke:#888,stroke-dasharray:5,5 说明 节点含义：每个节点i保存从i - lowbit(i) + 1到i区间的前缀和。索引关系： lowbit函数用于计算索引的最低位1，确定区间范围。例如：节点8保存[1,8]的和，节点4保存[1,4]的和。

---