下载文档原格式
第01讲什么是树状数组？树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。
有些同学会觉得很奇怪。
用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？但是，如果题目的A[]会改变呢？例如：我们来定义下列问题：我们有n个盒子。
可能的操作为1.向盒子k添加石块2.查询从盒子i到盒子j总的石块数自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。
但是用树状数组，对操作1和2的时间复杂度都为O(logn)。
第02讲图解树状数组C[]现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]网络上面都有这个图，但是我将这个图做了2点改进。
（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。
（2）C[i]为A[i]对应的那一列的最高的节点。
现在告诉你：序列C[]就是树状数组。
那么C[]如何求得？C[1]=A[1];C[2]=A[1]+A[2];C[3]=A[3];C[4]=A[1]+A[2]+A[3]+A[4];C[5]=A[5];C[6]=A[5]+A[6];C[7]=A[7];C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。
现在不得不引出关于二进制的一个规律：先仔细看下图：将十进制化成二进制，然后观察这些二进制数最右边1的位置：1 --> 000000012 --> 000000103 --> 000000114 --> 000001005 --> 000001016 --> 000001107 --> 000001118 --> 000010001的位置其实从我画的满二叉树中就可以看出来。
线段树之hdu4027Can you answer these queries?Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)Total Submission(s): 4014 Accepted Submission(s): 979Problem DescriptionA lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.Y ou are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.Notice that the square root operation should be rounded down to integer.InputThe input contains several test cases, terminated by EOF.For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. Y ou can assume that the sum of all endurance value is less than 263.The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.OutputFor each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.Sample Input101 2 3 4 5 6 7 8 9 1050 1 101 1 101 1 50 5 81 4 8Sample OutputCase #1:1976Source/*一个10^5的序列，有10^5个操作，每个操作为a,b,ca=0时将b到c区间内的数都开根号下取整,a=1时求b到c段的和其中所有数的和不超过2^63。
树状数组武钢三中 吴豪【引言】在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。
但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。
可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。
当n非常大时，程序会运行得非常缓慢。
因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。
【理论】为了对树状数组有个形 象的认识，我们先看下面这张图。
如图所示，红色矩形表示的数组C[]就是树状数组。
这里，C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，或者说是i用2的幂方和表示时的最小指数。
( 当然，利用位运算，我们可以直接计算出2^k=i&(i^(i-1)) ）同时，我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。
所以,当我们修改A[i]的值时，可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。
另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。
不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,因此，求和操作的复杂度也是O(logn)。
接着，我们考察这两种操作下标变化的规律：首先看修改操作：已知下标i，求其父节点的下标。
我们可以考虑对树从逻辑上转化：如图，我们将子树向右对称翻折，虚拟出一些空白结点（图中白色），将原树转化成完全二叉树。
有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。
因而父节点下标 p=i+2^k (2^k是i用2的幂方和展开式中的最小幂，即i为根节点子树的规模)即 p = i + i&(i^(i-1)) 。
接着对于求和操作：因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2的最小幂即可。
树常见题⽬总结1.树的前序遍历递归：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;preorder(ans,root);return ans;}void preorder(vector<int> &ans,TreeNode* root){if(root == NULL)return;ans.push_back(root->val);preorder(ans,root->left);preorder(ans,root->right);}};⾮递归：class Solution {public:vector<int> preorderTraversal(TreeNode* root){vector<int> res;stack<TreeNode*> tmp;if(root != NULL){tmp.push(root);}while(!tmp.empty()){res.push_back(tmp.top() -> val);root = tmp.top();tmp.pop();if(root -> right != NULL){tmp.push(root -> right);}if(root -> left != NULL){tmp.push(root -> left);}}return res;}};2.中序遍历递归：class Solution {public:vector<int>inorderTraversal(TreeNode* root){vector<int>res;inorder(root,res);return res;}void inorder(TreeNode* root,vector<int>& res){if(root == NULL){return;}inorder(root -> left,res);res.push_back(root -> val);inorder(root -> right,res);}};⾮递归：class Solution {public:vector<int> inorderTraversal(TreeNode* root) { vector<int> res;stack<TreeNode*>tmp;while(root != NULL || !tmp.empty()){if(root != NULL){tmp.push(root);root = root -> left;}else{root = tmp.top();res.push_back(root -> val);tmp.pop();root = root -> right;}}return res;}};3.后序遍历递归：class Solution {public:vector<int> postorderTraversal(TreeNode* root){ vector<int>res;postorder(res,root);return res;}void postorder(vector<int> &res,TreeNode* root){ if(root == NULL){return;}postorder(res,root -> left);postorder(res,root -> right);res.push_back(root -> val);}};⾮递归：class Solution {public:vector<int> postorderTraversal(TreeNode* root) { vector<int> res;stack<TreeNode*> tmp1;stack<TreeNode*> tmp2;if(root != NULL){tmp1.push(root);while(!tmp1.empty()){root = tmp1.top();tmp2.push(tmp1.top());tmp1.pop();if(root -> left != NULL)tmp1.push(root -> left);if(root -> right != NULL)tmp2.push(root -> right);}}while(!tmp2.empty()){res.push_back(tmp2.top() -> val);tmp2.pop();}return res;}};4.重建⼆叉树题⽬描述：输⼊某的前序遍历和中序遍历的结果，请重建出该⼆叉树。
数据结构…树形结构章节练习一.单项选择题1,如图所示的4棵二叉树中，_c_不是完全二叉树。
(A) (B) (C) (D)2.如图所示的4棵二叉树，_b_是平衡二叉树。
(A) (B) (C) (D)在线索化二叉树中，t所指结点没有左子树的充要条件是_b—。
A) t->left=NULL B) t->ltag= 1C) t->Itag=l且t->lcft=NULL D)以上都有不对二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法_b—oA)正确B)错误二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前而，这种说法_a—°A)正确B)错误由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_b—o A)正确B)错误设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_b—。
A) 2hB)2h-l C) 2h+l D)h+1如图所示二叉树的中序遍历序列是_b —。
A) abcdgef B) dfebage C) dbaefcg D) defbagc9•已知某二叉树的后序適历序列是dabec,中序遍历序列是debac,它的前序遍历序列是_d—°A) acbed B) decab C) deabc D) cedba如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的—。
A)前序B)中序C)后序D)层次序如果T2是由有序树T转换而来的二叉结，那么T中结点的后序就是T2中结点的_b—。
A)前序B )中序C)后序D)层次序某二叉树的前序遍历结点访问顺序是abdgcefh, 中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_d _____________________ 。
A) bdgcefha B) gdbecflia C) bdgaechf D) gdbehfca二叉树为二叉排序树的充分必要条件是其任一结点的值均大于英左孩子的值、小于其右孩子的值。
树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：令这棵树的结点编号为C1，。
令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3 C4 = A1 + A2 + A3 + A4C5 = A5C6 = A5 + A6C7 = A7C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8...C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16这里有一个有趣的性质：设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。
因为这个区间最后一个元素必然为Ax，所以很明显：Cn = A(n –2^k + 1) + ... + An算这个2^k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x){return x&(x^(x–1));}当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：step1:令sum = 0，转第二步；step2:假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；step3: 令n = n –lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：n = n –lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。
而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
树状数组维护区间和的模型及其拓广的简单总结by wyl8899树状数组的基本知识已经被讲到烂了，我就不多说了，下面直接给出基本操作的代码。
假定原数组为a[1..n]，树状数组b[1..n]，考虑灵活性的需要，代码使用int*a传数组。
#define lowbit(x)((x)&(-(x)))int sum(int*a,int x){int s=0;for(;x;x-=lowbit(x))s+=a[x];return s;}void update(int*a,int x,int w){for(;x<=n;x+=lowbit(x))a[x]+=w;}sum(x)返回原数组[1,x]的区间和，update(x,w)将原数组下标为x的数加上w。
这两个函数使用O(操作数*logn)的时间和O(n)的空间完成单点加减，区间求和的功能。
接下来做一些升级，让树状数组完成区间加减，单点查询的功能。
直接做的话很困难，需要对问题做一些转化。
考虑将原数组差分，即令d[i]=a[i]-a[i-1]，特别地，d[1]=a[1]。
此时a[i]=d[1]+..+d[i]，所以单点查询a[i]实际上就是在求d数组的[1..i]区间和。
而区间[l,r]整体加上k的操作，可以简单地使用d[l]+=k和d[r+1]-=k来完成。
于是，我们用树状数组来维护d[]，就可以解决问题了。
下面再升级一次，完成区间加减，区间求和的功能。
仍然沿用d数组，考虑a数组[1,x]区间和的计算。
d[1]被累加了x次，d[2]被累加了x-1次，...，d[x]被累加了1次。
因此得到sigma(a[i])=sigma{d[i]*(x-i+1)}=sigma{d[i]*(x+1)-d[i]*i}=(x+1)*sigma(d[i])-sigma(d[i]*i)所以我们再用树状数组维护一个数组d2[i]=d[i]*i，即可完成任务。
POJ3468就是这个功能的裸题，下面给出代码。
