线段树（Segment|线段树（Segment Tree）和树状数组（Fenwick Tree）线段树（SegmentTree）和树状数组

前言
在刷题过程中，经常会遇到求数组某区间之和的问题：给出数组a[0...n-1]，求数组下标i~j的元素之和a[i]+...+a[j]，0<=i<=j 纯暴力做法是O(n)，即把区间的数加起来。
好一点办法的是创建一个前缀和（prefix sum）数组p，使得p[i]=a[0]+...+a[i]，那么所求结果就是p[j]-p[i-1]，当然i=0需要特别处理一下。这样准备工作是O(n)，查询只需要O(1)。
一般来说，数组不变的情况下方法二已经够用了。但是当数组有可能改变的时候，每次改变都需要更新前缀和数组，效率不高。
好在，有专门的数据结构来满足这种操作需求。今天我们就来简单学习一下线段树（Segment Tree）和树状数组（Fenwick Tree）。
线段树
顾名思义，线段树是树。具体一点，二叉树。那么“线段”二字如何体现？是把i-j区间之和想象成i-j的线段（我瞎猜的）。简而言之，线段树就是把区间之和用树来显示。
很自然地，根是整个数组区间，然后左右分半，依次类推。奇数情况下是左边多还是右边多呢？其实都可以，不过考虑区间[a,b]，最自然的写法可分为[a,(a+b)/2]与[(a+b)/2,b]，当b-a是奇数时右边多，这样写起来更自然方便些。
从网上搜了个图，这样更直观：

线段树（Segment|线段树（Segment Tree）和树状数组（Fenwick Tree）
文章图片
image.png
怎么构造这棵树呢？
首先要决定树的节点。左右子节点等属性是很自然的。同时需要存储表示的区间，以及区间之和。
需不需要指针指向parent节点呢？大可不必。
至于重要的几个操作，构造，查询，更新，抓住递归的特点，自下而上地进行，一切都显得自然了。
构造：递归，先构造左右，再构造自己，这样其实是从底层往上构造。
查询：同样递归，假如查询的区间就是自己马上返回，否则就有三种情况：查询左边，查询右边，两边都有。
更新：和查询类似，不同的是一次只更新一个元素，所以只会走一边。路径相当于查询[i,i]，下到最底层更新值。注意路径之上的节点也要跟着更新和。
当然了，start和end在这里是inclusive的，和java传统惯例有点不一样，但是这系列的习惯好像就这样，毕竟要表示单个元素。树的高度是O(logn)，而查询操作近似遍历树，所以也是O(logn)。更新操作类似，同样是O(logn)。构造的话，要把节点都过一遍，所以是O(n)。代码如下：

class SegmentTree {private static class TreeNode { int start, end, sum; TreeNode left, right; TreeNode(int start, int end) { this.start = start; this.end = end; } }private TreeNode buildTree(int[] nums, int start, int end) { if (start > end) return null; TreeNode cur = new TreeNode(start, end); if (start == end) cur.sum = nums[start]; else { int mid = start + (end - start) / 2; cur.left = buildTree(nums, start, mid); cur.right = buildTree(nums, mid + 1, end); cur.sum = cur.left.sum + cur.right.sum; } return cur; }private void updateTree(TreeNode node, int i, int val) { if (node.start == node.end) { node.sum = val; } else { int mid = node.start + (node.end - node.start) / 2; if (i <= mid) updateTree(node.left, i, val); else updateTree(node.right, i, val); node.sum = node.left.sum + node.right.sum; } }private int queryTree(TreeNode node, int i, int j) { if (node.start == i && node.end == j) return node.sum; else { int mid = node.start + (node.end - node.start) / 2; if (j <= mid) { return queryTree(node.left, i, j); } else if (i >= (mid + 1)) { return queryTree(node.right, i, j); } else { return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j); } } }private TreeNode root; SegmentTree(int[] nums) { root = buildTree(nums, 0, nums.length - 1); }public void update(int i, int val) { updateTree(root, i, val); }public int sumRange(int i, int j) { return queryTree(root, i, j); } }

代码量还是不小的，毕竟用了树。
树状数组
树状数组（也叫Binary Indexed Tree）就是指用数组来表示一棵树，这样空间上更节约。类似的还有binary heap。
那么树怎么放进数组呢？根据维基百科，对于数组里的下标i进行一个特定的位运算，就可以获得其父节点所在的下标。听起来很神奇？刚开始我也不知所云，直到看了Competitive Programming Algorithms的解释：

线段树（Segment|线段树（Segment Tree）和树状数组（Fenwick Tree）

文章图片
image.png
翻译一下。本质上我们需要的就是一个函数g，使得0<=g(i)<=i，这样的话假如T[i]=A[g(i)]+...+A[i]，我们想要求i的前缀和，因为已经有了g(i)之后的了，于是往前看，右边界就是g(i)-1，那么左边界是哪里呢？自然还是利用g函数，也就是说前一段是A[g(g(i)-1)]+...+A[g(i)-1]，根据定义这就是T[g(i)-1]。然后依次类推直至到0。
这样时间复杂度主要取决于g函数。假如g(i)=i，那么T=A；假如g(i)=0，那么T就是前缀和数组。这些我们都知道并不是最优选择。所以这个数据结构巧妙的地方就在于g函数的设定，使得查询和更新都能达到O(logn)的效率。
g(i)的定义：将i二进制表示的末尾的连续的1全部换成0，例如g(0b1001)=0b1000，g(0b1100)=0b1100，g(0b1111)=0。或者可以用位运算阐释： g(i)=i&(i+1)。
除此之外，我们还需要一个运算来更新。因为假如要更新i下标，我们得知道这个i到底在哪一段上，也就是说要找到所有的j，使得g(j)<=i<=j，然后更新T[j]。假设这个运算为h。 h(j)=j|(j+1)。以i=10为例，第一个j自然是i本身，然后就是h(0b1010)=0b1011=11，而g(0b1011)=0b1000=8小于10满足条件；下一个是h(0b1011)=15，同样满足条件。通过几个例子可以看出，j|(j+1)肯定是大于等于j的。
同样引用cp-algo里面的图，绿色代表T涵盖的范围：

文章图片
image.png
值得注意的一点是这里的T下标是从0开始的，也可以从1开始。
什么意思呢？之前往前推，我们需要用g(i)-1，那么假如我们直接让T[i]=|g(i)+1,i|范围的和，往前推就直接是g(i)了，更方便。但是这样有一个问题，就是i=0的时候不满足之前的假设。因此，我们让T下标都增加1，也就是说其实T[1]对应的是A[0]，T[0]是0。
g和h函数也要相应调整。 g(i)=i?(i & (?i))也就是把最后一个1变为0. h(i)=i+(i & (?i))即最后一个1进位。此写法显得更对称一些，因此网上大多采用这种。
代码实现：

class BinaryIndexedTree {private final int[] BITree, arr; public BinaryIndexedTree(int[] arr) { this.arr = arr; BITree = new int[arr.length + 1]; for (int i = 0; i < arr.length; i++) updateBIT(i, arr[i]); }public int sumRange(int i, int j) { return getSum(j) - getSum(i - 1); }public void update(int i, int val) { int delta = val - arr[i]; arr[i] = val; updateBIT(i, delta); }private void updateBIT(int index, int delta) { index++; while (index < BITree.length) { BITree[index] += delta; index += index & (-index); } }private int getSum(int index) { int sum = 0; index++; while (index > 0) { sum += BITree[index]; index -= index & (-index); } return sum; } }

可见，其实树状数组并不是简单地把线段树装进数组，而是有另一套计算方法，差别还是挺明显的。
相比之下，树状数组代码量更少，更高效，一般来说是更好的选择。
例题
【线段树（Segment|线段树（Segment Tree）和树状数组（Fenwick Tree）】Range Sum Query - Mutable - LeetCode
以上两种实现改个名字就可以直接当答案了。