SnowKagura‘s blog - ans
type: channel
link: https://www.snowkagura.com/tag/ans/
items: 数据结构——树状数组小结
items: 记Leetcode一题——二叉树寻路

数据结构——树状数组小结
type: item
date: 2022-05-26T16:37:00+08:00
description: 适用场景树状数组是一种适用于多次单点修改统计区间和问题的数据结构。基本思想Binary Indexed Tree 求和的基本思想在于，给定需要求和的位置 i ，例如 13 ，我们可以利用其二进制表示法来进行分段（或者说分层）求和：13 = 2^3 + 2^2 + 2^0，则prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13) （注意此处的RANGE(x, y)表示数组中第x个位置到第y个位置的所有数字求和）。如下面例子中所示：arr = [1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5] prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13) = 29 + 10 + 4 = 43那么只要我们提前计算好这些RANGE(x,y)，便可以对相应的序列进行快速求和。下面是构造树状数组的方法（填坑法）：图中最上面是原数组，中间代表了树状数组各元素的意义，即RANGE(x,y)，而最下面便是原数组对应的树状数组。利用树状数组求区间和利用树状数组，我们可以发现：prefixSum(13) = prefixSum(0b00001101) = BIT[13] + BIT[12] + BIT[8] = BIT[0b00001101] + BIT[0b00001100] + BIT[0b00001000]其中BIT即树状数组，而从二进制位我们可以发现一个很有意思的结论，即我们实际上是在将下标13每次减少一个最低位的1所在位对应的数字，直到小于1为止，将这些下标对应的元素累加起来便是RANGE(1,13)的和。总结起来就像这样：这个结构可以抽象成一颗树一样：寻找父节点的操作便是lowbit ，也即上述所发现的结论，假设当前节点下标为 x ，则 lowbit(x) = x & -x。这样，我们就可以通过树状数组快速求区间和了。更新数组中的元素而关于如何进行单点修改，我们以update(5,2)为例：我们可以发现，单点修改的过程恰好与求区间和的过程相反，在此处，我们需要从5开始，对5进行lowbit的增加，直至超出数组范围，对所经过的下标对应的元素均进行累加，即可完成一次单点修改。树状数组的建立第一种方法很简单，遍历数组中的每一个元素，对其使用update(i + 1, elem)即可，这是一种O(nlog n)时间复杂度的构造方法第二种方法是一种时间复杂度O(n)的方法，其步骤如下(数组下标从0开始)：给定一个长度为n的输入数组list。初始化长度为n + 1的Binary Indexed Tree数组bit，并将list中的数字对应地放在bit[1]到bit[n]的各个位置。对于1到n的每一个i，进行如下操作：令j = i + (i & -i)，若j < n + 1，则bit[j] = bit[j] + bit[i]代码实现class BinaryIndexTree { private: int *tr; inline int lowbit(int x) { return x & -x; } public: BinaryIndexTree(int arr[], int n) { tr = new int[n + 1]; for (int i = 0; i < n; ++i) tr[i + 1] = arr[i]; for (int i = 1; i < n + 1; ++i) { int j = lowbit(i); if (j < n + 1) tr[j] += tr[i]; } } void add(int x, int v) { for(int i = x; i < n + 1; i += lowbit(i)) tr[i] += v; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } }参考文章树状数组（Binary Indexed Tree），看这一篇就够了

记Leetcode一题——二叉树寻路
type: item
date: 2021-07-29T15:36:00+08:00
description: 题目描述：在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。示例：输入：label = 14输出：[1,3,4,14]这道题刚看到，我其实是没有很多思路的，我在想，难不成要把树的结构给建出来然后用dfs算法来做吗？想想觉得还是太过于笨重了，于是跑去评论区看了看，首先映入眼帘的就是牛逼的位运算解法，理解之后感觉真的是非常的奇妙。解法一：主要思路是这样的：首先，知道我们要找的数字label，因为二叉树的结构，每向下深入一层，实际上就是加上2的depth次幂，那么便有将label转换成二进制，向右移动一位，此时的最高位即为label的上一层的第一个数字，又因为该树状图是之字形排列，那么仅仅将其右移一位得到的并不是label的父节点，而是其父节点的对称位置的节点，那么如何才能得到父节点的数字呢？这时候就有一个精妙的操作，将除了最高位以外的所有位进行反转，这样便得到了当前数字的对称位置的数字。然后重复以上步骤便可以得到答案。class Solution { public: vector<int> pathInZigZagTree(int label) { vector<int> ans; while (label != 1) { ans.push_back(label); label >>= 1; //这里实际上就是获取当前label的二进制位数然后减1可以使得除最高位以外的所有数字为1，那么进行异或就 //会得到反转的效果 label = label ^ (1 << ((int)log2(label))) - 1; } ans.push_back(1); reverse(ans.begin(), ans.end()); return ans; } };解法二：还有一种解法就是数学归纳法了，通过观察其实可以得到以下规律，label的父节点即为上一层的最后一个数减掉当前label到当前层数的第一个数的距离除以二。代码如下：class Solution { public: vector<int> pathInZigZagTree(int label) { int depth = log(label) / log(2); vector<int> ans; ans.push_back(label); for (int i = depth; i > 0; --i) { int edge = pow(2, i); label = edge - 1 - (label - edge) / 2;//核心语句 ans.push_back(label); } reverse(ans.begin(),ans.end()); return ans; } };最近刷一刷leetcode，感觉算法也不是那样的枯燥无味了，要坚持每天进步一点点，总有一天能跨过算法与数据结构的大关的