# 数据结构Advanced ## Index * [树状数组](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#树状数组) * [树状数组的构建（以区间和问题为例）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#树状数组的构建以区间和问题为例) * [树状数组的特点](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#树状数组的特点) * [相关问题](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#相关问题) * [相关阅读](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#相关阅读) * [线段树](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#线段树) * [字典树（Trie）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#字典树trie) * [数据结构设计](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#数据结构设计) * [LRU 缓存](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xArfG0s6gyf0Dqk#lru-缓存) ## 树状数组 * 树状数组是一种用于维护**前缀信息**的数据结构 * 树状数组 `C` 在物理空间上是连续的； * 对于数组中的两个位置 `C[x], C[y]`，若满足 `y = x + 2^k`（**其中** `k` **表示** `x` **二进制中末尾 0 的个数**），则定义 `C[x], C[y]` 为一组父子关系； ``` 4 的二进制为 100，则 k = 2 所以 4 是 4 + 2^2 = 8 的孩子 5 的二进制位 101，则 k = 0 所以 5 是 5 + 2^0 = 6 的孩子 ``` * 由以上定义，可知**奇数**下标的位置一定是叶子节点 **C\[i] 的直观含义** * `C[i]` 实际上表示原数组中一段**区间**内的**某个统计意义**（区间和、区间积、区间最值等等）； * 该区间为 `[i-2^k+1, i]`，是一个闭区间； * 以**区间和**为例 ``` 1=(001) C[1]=A[1]; 2=(010) C[2]=A[1]+A[2]; 3=(011) C[3]=A[3]; 4=(100) C[4]=A[1]+A[2]+A[3]+A[4]; 5=(101) C[5]=A[5]; 6=(110) C[6]=A[5]+A[6]; 7=(111) C[7]=A[7]; 8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; ``` ### 树状数组的构建（以区间和问题为例） > LeetCode - [307. 区域和检索 - 数组可修改](https://leetcode-cn.com/problems/range-sum-query-mutable/description/) **问题描述** ``` 给定一个数组，支持两种操作： 1.查询区间和 2.修改某个元素的值 示例： Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8 ``` * 构建树状数组的过程即初始化数组 `C` 的过程 * 基本操作： * `lowbit(x)` ——求 2^k，其中 k 表示 x 二进制位中后缀 0 的个数 * `updateC(x, delta)` ——更新 C 数组中 A\[x] 的祖先 * 如果是初始化阶段 delta = A\[i]， * 如果是更新 A\[i]，则 delta = new\_val - A\[i] * `sumPrefix(x)` ——求前缀区间 \[1, x] 的和 * `update(i, val)` ——更新 A\[i] = val，同时也会更新所有 A\[i] 的祖先 * `sumRange(lo, hi)` ——求范围 \[lo, hi] 的区间和 **C++** ```cpp class NumArray { int n; vector A; vector C; // 求 2^k，其中 k 表示 x 二进制位中后缀 0 的个数 int lowbit(int x) { return x & (-x); } // 更新 C 数组，对 A[x] 的每个祖先都加上 delta： // 如果是初始化阶段 delta = A[i]，如果是更新 A[i]，则 delta = new_val - A[i] void updateC(int x, int delta) { for (int i = x; i <= n; i += lowbit(i)) { C[i] += delta; } } // 求前缀区间 [1, x] 的和 int sumPrefix(int x) { int res = 0; for (int i = x; i > 0; i -= lowbit(i)) { res += C[i]; } return res; } public: // 初始化 NumArray(vector nums) { n = nums.size(); A.resize(n + 1, 0); C.resize(n + 1, 0); for (int i = 1; i <= n; i++) { A[i] = nums[i - 1]; // 树状数组的内部默认从 1 开始计数 updateC(i, A[i]); } } // 将 A[i] 的值更新为 val void update(int i, int val) { i++; // 树状数组的内部默认从 1 开始计数，如果外部默认从 0 开始计数，则需要 +1; updateC(i, val - A[i]); // 更新 A[i] 的所有祖先节点，加上 val 与 A[i] 的差即可 A[i] = val; } // 求范围 [lo, hi] 的区间和 int sumRange(int lo, int hi) { lo++; hi++; // 树状数组的内部默认从 1 开始计数，如果外部默认从 0 开始计数，则需要 +1; return sumPrefix(hi) - sumPrefix(lo - 1); } }; void solve() { vector nums{1, 3, 5}; auto na = NumArray(nums); int ret; ret = na.sumRange(0, 2); na.update(1, 2); ret = na.sumRange(0, 2); } ``` ### 树状数组的特点 * 线段树不能解决的问题，树状数组也无法解决； * 树状数组和线段树的时间复杂度相同：初始化 `O(n)`，查询和修改 `O(logn)`；但实际效率要高于线段树； * 直接维护前缀信息也能解决查询问题，但是修改的时间复杂度会比较高； ### 相关问题 * [665. 二维区域和检索 - 矩阵不可变](https://www.lintcode.com/problem/range-sum-query-2d-immutable/description) - LintCode * [817. 二维区域和检索 - 矩阵可变](https://www.lintcode.com/problem/range-sum-query-2d-mutable/description) - LintCode * [249. 统计前面比自己小的数的个数](https://www.lintcode.com/problem/count-of-smaller-number-before-itself/description) - LintCode * [248. 统计比给定整数小的数的个数](https://www.lintcode.com/problem/count-of-smaller-number/description) - LintCode * [532. 逆序对](https://www.lintcode.com/problem/reverse-pairs/description) - LintCode ### 相关阅读 * [夜深人静写算法（三）- 树状数组](https://blog.csdn.net/WhereIsHeroFrom/article/details/78922383) - CSDN博客 ## 数据结构设计 ### LRU 缓存 > LeetCode/[146. LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/description/) **思路** * **双向链表** + haspmap * 数据除了被保存在链表中，同时也保存在 map 中；前者用于记录数据的顺序结构，后者以实现 `O(1)` 的访问。 * **更新过程**： * 新数据插入到链表头部 * 每当缓存命中（即缓存数据被访问），则将数据移到链表头部 * 当链表满的时候，将链表尾部的数据丢弃 * **操作**： * `put(key, value)`：如果 key 在 hash\_map 中存在，则先**重置对应的 value 值**，然后获取对应的节点，将节点从链表移除，并移动到链表的头部；若果 key 在 hash\_map 不存在，则新建一个节点，并将节点放到链表的头部。当 Cache 存满的时候，将链表最后一个节点删除。 * `get(key)`：如果 key 在 hash\_map 中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。 **C++**（AC） ```cpp // 缓存节点（双端队列） struct CacheNode { int key; int value; CacheNode *pre, *next; CacheNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {} }; class LRUCache { int size = 0; CacheNode* head = nullptr; CacheNode* tail = nullptr; unordered_map dp; // hash_map void remove(CacheNode *node) { if (node != head) { // 修改后序节点是需判断是否头结点 node->pre->next = node->next; } else { head = node->next; } if (node != tail) { // 修改前序节点是需判断是否尾结点 node->next->pre = node->pre; } else { tail = node->pre; } // remove 时不销毁该节点 //delete node; //node = nullptr; } void setHead(CacheNode *node) { node->next = head; node->pre = nullptr; if (head != nullptr) { head->pre = node; } head = node; if (tail == nullptr) { tail = head; } } public: LRUCache(int capacity) : size(capacity) { } int get(int key) { auto it = dp.find(key); if (it != dp.end()) { auto node = dp[key]; // 如果命中了，把该节点移动到头部 remove(node); setHead(node); return node->value; } return -1; } void put(int key, int value) { auto it = dp.find(key); if (it != dp.end()) { auto node = dp[key]; node->value = value; // 更新 remove(node); setHead(node); } else { auto node = new CacheNode(key, value); setHead(node); dp[key] = node; // 关键：判断容量 //if (dp.size() >= size) { // 若先删除节点，则为 >= if (dp.size() > size) { // 若先存入 dp，则为 > auto it = dp.find(tail->key); remove(tail); // 这里才销毁内存（即使不销毁也能过 LeetCode） delete it->second; it->second = nullptr; dp.erase(it); // 先销毁，在移除 } } } }; ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/zhuan-tiashu-ju-jie-gou-advanced.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.