下载文档原格式
第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就是这个功能的裸题，下面给出代码。
树状数组是一个查询和修改复杂度都为log(n)级别的区间统计的数据结构，在思想上类似于线段树。
相比线段树，树状数组需要的空间较少，编程复杂度也较低，但适用范围比线段树小。
来观察一下这个图：令这棵树的结点编号为C1，。
令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3C4 = 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));}利用机器补码的特点，这个函数可以改得更方便int lowbit(int i){return i&(-i);}如果要把a[n]增加m，可以通过调用如下函数实现void add(int i,int v){while (i<=n){a[i]+=v;i+=lowbit(i);}}如果要统计a[1]到a[n]之间的和，可以通过调用如下函数实现int sum(int i){int s=0;while (i>0){s+=a[i];i-=lowbit(i);}return s;}这是一维的情况，很容易能推广到二维。
POJ上用到树状数组的题目：poj2352 Starspoj2481 Cowspoj1195 Mobile phonespoj3067 Japanpoj2155 Matrixpoj2464 Brownie Points II(以下是经典)树状数组是一种非常优雅的数据结构.当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.假设a[1...N]为原数组,定义c[1...N]为对应的树状数组:c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i]其中k为i的二进制表示末尾0的个数,所以2^k即为i的二进制表示的最后一个1的权值. 所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n):int lowbit(int n){return n& (-n);}对a[n]进行修改后,需要相应的修改c数组中的p1, p2, p3...等一系列元素其中p1= n,p i+1= p i+ lowbit(p i)所以修改原数组中的第n个元素可以实现为:void Modify(int n, int delta){while(n <= N){ c[n] += delta; n += lowbit(n);}}当要查询a[1],a[2]...a[n]的元素之和时,需要累加c数组中的q1, q2, q3...等一系列元素其中q1 = n,q i+1= q i - lowbit(q i)所以计算a[1] + a[2] + .. a[n]可以实现为:int Sum(int n){int result = 0;while(n != 0){ result += c[n]; n -= lowbit(n); }return result;}树状数组可以扩充到二维。
用树状解决高中数学树形问题方法全解析高中数学中的树形问题是指那些需要利用树状图进行求解的问题。
这种问题通常需要我们建立一棵树，并对其进行一系列的操作。
本文将介绍如何用树状解决高中数学树形问题，包括建立树状图、进行递归求解、优化算法等方面的内容。
下文将一一阐述。
1. 建立树状图树状图是树形问题的基础。
对于一个给定的问题，我们需要首先确定树状图的结构。
具体来说，我们需要确定每个节点代表的含义以及节点之间的关系。
通常情况下，我们可以将树状图分为以下几类：（1）有根树：有根树是指一棵树中有一个节点被指定为根节点。
根节点没有父节点，而其他节点都有唯一的父节点。
有根树可以用于解决许多问题，例如二叉树、树状数组等。
（2）无根树：无根树是指一棵树中没有被指定为根节点的节点。
每个节点都有若干个子节点和若干个父节点。
无根树通常用于解决一些比较基础的问题，例如最长上升子序列、最长公共子序列等。
（3）有向无环图（DAG）：DAG 是指一类图，其中每条边都是有向的，并且不存在环。
DAG 通常用于解决一些比较复杂的问题，例如最长路问题、拓扑排序等。
2. 递归求解递归是解决树形问题的常用方法。
具体来说，我们可以利用递归的方式对树进行遍历，同时在遍历的过程中计算出问题的答案。
对于每个节点，我们可以假设其已经知道了所有子节点的答案，然后利用这些答案计算出当前节点的答案。
最终，我们可以利用递归的方式计算出整个树的答案。
3. 优化算法在实际应用中，我们经常需要对树形问题进行优化。
下面介绍一些常用的优化算法。
（1）记忆化搜索：记忆化搜索是指在递归求解的过程中，将已经求解过的子问题的答案进行记录，从而避免重复计算。
记忆化搜索常用于一些比较复杂的树形问题，例如最长路问题、最大权闭合子图等。
（2）动态规划：动态规划是一种常用的优化算法，它通常用于求解一些具有重叠子问题的问题。
在树形问题中，我们可以将整个树看作一棵 DAG，然后利用动态规划的方式求解问题。
树状数组习题（⼀本通）1535：【例 1】数列操作模板题#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<cstdio>#include<queue>#include<map>#include<vector>#include<set>using namespace std;const int maxn=101000;const int INF=0x3fffffff;typedef long long LL;#define lowbit(x) ((x)&(-x))int tree[maxn];int n,m;void add(int x,int d){while(x<=n){tree[x]+=d;x+=lowbit(x);}}LL getsu(int x){LL ans=0;while(x>0){ans+=tree[x];x-=lowbit(x);}return ans;}int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) {int x;scanf("%d",&x);add(i,x);}int k,a,b;while(m--){scanf("%d %d %d",&k,&a,&b);if(k==0) printf("%lld\n",getsu(b)-getsu(a-1));else add(a,b);}return 0;}1536：【例 2】数星星 Stars//⼆维的树状数组bushi//认真读题呀看给出数据的特征，是按照纵坐标从⼩到⼤排序的，纵坐标相同的是横坐标从⼩到⼤给出的//也就是说，我们可以不管纵坐标，按照它给出的横坐标依次插⼊，并统计当前星星之前的横坐标⼩于它的星星个数。
树状数组三道模板题⼩结今天写了⼀天北京信息科技⼤学，难度不⼤，跟西电校赛风格类似，⼤部分为数学题与规律题。
（改⽇更）其中的I题为树状数组/线段树模板题，发现之前没有在博客总结，⼀时也找不到好的模板，于是重新深⼊学习了⼀番。
⾸先引⼊洛⾕上的模板题：P3374 【模板】树状数组 1题⽬描述如题，已知⼀个数列，你需要进⾏下⾯两种操作：1.将某⼀个数加上x2.求出某区间每⼀个数的和输⼊输出格式输⼊格式：第⼀⾏包含两个整数N、M，分别表⽰该数列数字的个数和操作的总个数。
第⼆⾏包含N个⽤空格分隔的整数，其中第i个数字表⽰数列第i项的初始值。
接下来M⾏每⾏包含3个整数，表⽰⼀个操作，具体如下：操作1：格式：1 x k 含义：将第x个数加上k操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和输出格式：输出包含若⼲⾏整数，即为所有操作2的结果。
说明时空限制：1000ms,128M数据规模：对于30%的数据：N<=8，M<=10对于70%的数据：N<=10000，M<=10000对于100%的数据：N<=500000，M<=500000题解由于是【单点修改，区间查询】裸题，就直接上AC代码了：#include<iostream>#include<cstdio>using namespace std;#define lowbit(x) ((x)&(-x))int n, m;int C[500010]; // 树状数组只需要开⼀倍内存空间int sum(int x) {int res = 0;while(x) {res += C[x];x -= lowbit(x);}return res;}void add(int x, int d) {while(x<=n) {C[x] += d;x += lowbit(x);}}int main() {cin>>n>>m;for(int i=1;i<=n;i++) {int ai;scanf("%d", &ai);add(i, ai);}while(m--) {int q, x, y;scanf("%d %d %d", &q, &x, &y);if(q==1) {add(x, y);}else if(q==2) {printf("%d\n", sum(y)-sum(x-1));}}return0;}P3368 【模板】树状数组 2题⽬描述如题，已知⼀个数列，你需要进⾏下⾯两种操作：1.将某区间每⼀个数数加上x2.求出某⼀个数的值输⼊输出格式输⼊格式：第⼀⾏包含两个整数N、M，分别表⽰该数列数字的个数和操作的总个数。
逆序对设A[1…n]是一个包含n个不同数的数组。
如果在i<j的情况下，有A[i]>A[j]，则（i，j）就称为A中的一个逆序对（inversion）【《算法导论》2-4】现给出一个数列，求该数列中的逆序对数（逆序数）。
本节给出三种方法：方法一是最直接的暴力方法；方法二是基于归并分治的思想；方法三是基于线段树的。
【解法一】暴力方法最直接，也最容易想到，两层for循环就可以算出来逆序数：每遇到一个元素回头遍历寻找比其大的元素个数即可，当然向后寻找比其小的元素个数也可以，复杂度为O(n^2)，代码：[cpp]view plaincopy1.int sum = 0;2.for(int i = 0; i < size; ++i)3.{4. for(int j = i+1; j < size; ++j)5. {6. if(arr[i] > arr[j])7. {8. ++sum;9. }10. }11.}12.return sum;【解法二】这种方法最初见于《算法导论》，这里先附上《算法导论》2-4关于逆序对的几点讨论：1）如果数组的元素取自集合[1,2,…,n]，那么，怎样的数组含有最多的逆序对？它包含多少个逆序对？析：很容易想到，当一个数列为逆序时，即[n,n-1,n-2,…,1]，逆序数是最多的，是多少？当 n=1，inversion=0；n=2，inversion在原来基础上增加1；n=3，inversion增加2…n=n时，inversion增加 n-1，所以总的inversion为等差求和n(n-1)/2；也可以这样理解，数列[n,n-1,n-2,…,1]中任取两个数皆为逆序2，即n(n-1)/2。
对，故逆序数为Cn2）插入排序的运行时间与输入数组中逆序对的数量之间有怎样的关系？析：我们知道插入排序的程序如下[cpp]view plaincopy1.for(int i = 1; i < n; ++i)2.{3. int key = arr[i];4. for(int j = i; j > 0 && arr[j-1] > key; --j)5. {6. arr[j] = arr[j-1];7. }8. arr[j] = key;9.}可以看出，每次内层循环都尝试将当前元素放在“合适”的位置上，所以对于内层循环的每一次迭代，都是在消除当前元素相对之前元素所对应的一系列逆序对，故总的循环便是消除数列所有的逆序对；3）给出一个算法，它能用O(nlgn)的最坏运行时间，确定n个元素的任何排列中逆序对的数目。
树状数组的模板题【如果你不知道什么是树状数组：这是⼀道模板题。
给定数列a1,a2,…,a n，你需要进⾏m各操作，操作有两类：1 i x：给定i,x，将a i加上x；2 l r：给定l.r，求Σr i=l a i的值（换⾔之，求a l+a l+1+⋯+a r的值）。
输⼊格式第⼀⾏包含2个正整数n,m，表⽰数列长度和询问个数。
保证1≤n,m≤106。
第⼆⾏n个整数a1,a2,…,a n，表⽰初始数列。
保证|a i|≤106。
接下来m⾏，每⾏⼀个操作，为以下两种之⼀：1 i x：给定i,x，将a i加上x；2 l r：给定l.r，求Σr i=l a i的值。
保证1≤l≤r≤n,|x|≤106。
输出格式对于每个2 l r操作输出⼀⾏，每⾏有⼀个整数，表⽰所求的结果。
思路：这是⼀道简单的⼀维树状数组的模板题#include <bits/stdc++.h>using namespace std;typedef long long ll;#define endl '\n'#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#define _for(i, a, b) for (int i=(a); i<=(b); i++)const int INF = 0x7fffffff;const int MAXN = 1e6 + 10;ll tree[MAXN], n, m;inline ll lowbit(ll x){return x & (-x);}void updata(ll x, ll d){while(x <= n){tree[x] += d;x += lowbit(x);}}ll getsum(ll x){ll res = 0;while(x > 0){res += tree[x];x -= lowbit(x);}return res;}int main(){IOScin >> n >> m;_for(i, 1, n){ll a;cin >> a;updata(i,a);}while(m--){ll id, x, y;cin >> id >> x >> y;if(id == 1){updata(x,y);}else if(id == 2){cout << getsum(y) - getsum(x-1) << endl;}}return 0;}这是⼀道模板题。
树状数组题目
1.单点修改，区间查询
给定一个长度为n的数组a，支持单点修改和查询区间和，即： - void modify(int i, int x)：将a[i]修改为x。
- int query(int l, int r)：返回a[l]+a[l+1]+...+a[r]。
使用树状数组（或线段树）实现该数据结构。
2. 区间修改，单点查询
给定一个长度为n的数组a，支持区间修改和查询单个元素，即： - void modify(int l, int r, int x)：将a[l]~a[r]都加上x。
- int query(int i)：返回a[i]的值。
使用树状数组（或线段树）实现该数据结构。
3. 数组前缀和
给定一个长度为n的数组a，支持查询前缀和，即：
- int query(int i)：返回a[0]+a[1]+...+a[i]。
使用树状数组（或前缀和数组）实现该数据结构。
4. 数组后缀和
给定一个长度为n的数组a，支持查询后缀和，即：
- int query(int i)：返回a[i]+a[i+1]+...+a[n-1]。
使用树状数组（或前缀和数组）实现该数据结构。
- 1 -。
