1701 【树状数组】数星星(POJ2352 star) 1702 【树状数组】矩阵(POJ 2155)

第二题：火柴排队（贪心+逆序对）对距离公式化简得：∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi要求∑(ai-bi)^2最小，就只需要∑aibi最大即可。

这里有个贪心，当a1<a2<…<an,b1<b2<..<bn时，∑aibi最大。

证明如下：若存在a>b,c>d,且ac+bd<ad+bc，则a(c-d)<b(c-d),则a<b，与a>b 矛盾，所以若a>b,c>d，则ac+bd>ad+bc将此式子进行推广：当a1<a2<a3<...<an ,b1<b2<...<bn的情况下∑aibi最大，即∑(ai-bi)^2最小。

然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。

例如：对于数据：42 3 1 43 2 1 4先排序:1 2 3 41 2 3 4保持序列1不动，那么序列2中的3就对应序列1中的2位置，2就对应序列1中的1位置，1就对应序列1中的3位置，4就对应序列1中的4位置，那么重定义数组为：2 13 400这个序列的逆序对为(2,1),所以答案是1。

求逆序对方法：1.归并排序2.把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同时查询比这个数大的数有几个，加入答案。

复杂度: O(n log n)代码（C++）（树状数组）：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define MAXN 100010#define lowbit(x)(((~(x))+1)&x)#define MAX 99999997struct saver{int v,t;};saver a[MAXN],b[MAXN];bool cmp(saver x,saver y){return x.v<y.v;}int n,r[MAXN],ans=0;int t[MAXN];void Add(int x){for(int i=x;i<=n;i+=lowbit(i)) t[i]++;}int Sum(int x){int rec=0;for(;x;x-=lowbit(x)) rec+=t[x];return rec;}int main(){scanf("%d",&n);for(int i=0;i++<n;)scanf("%d",&a[i].v),a[i].t=i;for(int i=0;i++<n;)scanf("%d",&b[i].v),b[i].t=i;sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);for(int i=0;i++<n;) r[a[i].t]=b[i].t;for(int i=n;i;i--) ans+=Sum(r[i]),Add(r[i]),ans%=MAX;printf("%d\n",ans);return 0;}2.这道题明显可以用类似最长上升子序列的动态规划求解，易得思路如下：用f(i,0)表示以i为结尾的且最后一段上升的子序列最大长度，f(i,1)表示表示以i为结尾的且最后一段下降的子序列最大长度，那么答案明显就是max{f(i,0),f(i,1)} 方程：f(i,0)=max{f(j,1)}+1 0<=j<i且h[j]<h[i]f(i,1)=max{f(j,0)}+1 0<=j<i且h[j]>h[i]边界：f(0,0)=f(0,1)=0如果直接DP毫无疑问复杂度是O(n^2)，会TLE，但是，考虑到我们每次取最值时候取得都是一个区间里的数，如f(i,0)=max{f(j,1)}+1 0<=j<i且h[j]<h[i]取得就是区间[0,h[i]-1]里的最值，所以可以使用线段树或者是BIT（树状数组）来优化，这样复杂度就是O(n log n)，可以过全部数据。

苏教版科学二年级上册第6课《数星星》说课稿9一. 教材分析《数星星》是苏教版科学二年级上册第6课的内容。

本节课通过数星星的活动，让学生感知到数的产生和数的运用，培养学生的数感和逻辑思维能力。

教材以学生的生活经验为基础，设计了一系列的操作活动，让学生在实际操作中感受数的产生和运用，提高学生的数学素养。

二. 学情分析二年级的学生已经具备了一定的数数能力，对数的概念有了一定的了解。

但他们对于数的产生和数的运用还不是很清楚，需要通过具体的操作活动来进一步理解和掌握。

此外，学生对于星星的认知也存在差异，有的学生对星星的了解比较多，有的学生可能不太了解。

因此，在教学过程中，需要关注学生的个体差异，尽量让每个学生都能参与到课堂活动中来。

三. 说教学目标1.知识与技能：学生会数星星，理解数的产生和运用，培养数感。

2.过程与方法：学生通过观察、操作、交流等活动，学会用数来描述和表达现实世界中的事物和现象。

3.情感态度与价值观：学生体验数星星的乐趣，培养对数学的兴趣和好奇心。

四. 说教学重难点1.教学重点：学生会数星星，理解数的产生和运用。

2.教学难点：学生用数来描述和表达现实世界中的事物和现象。

五. 说教学方法与手段本节课采用情境教学法、游戏教学法和小组合作学习法。

情境教学法通过数星星的活动，让学生在实际操作中感受数的产生和运用；游戏教学法通过趣味性的游戏，激发学生的学习兴趣；小组合作学习法让学生在小组讨论和合作中，提高解决问题的能力。

此外，利用多媒体课件和实物模型辅助教学，帮助学生更好地理解和掌握知识。

六. 说教学过程1.导入：通过展示夜空中的星星，引导学生观察星星的数量，激发学生数星星的兴趣。

2.数星星：学生分组数星星，记录数星星的结果。

教师巡回指导，帮助学生解决数星星过程中遇到的问题。

3.讨论数的产生和运用：学生汇报数星星的结果，教师引导学生讨论数的产生和运用，让学生理解数的作用。

4.游戏：学生参与数星星的游戏，巩固对数的理解和运用。

树状数组简单易懂的详解1 什么是树状数组树状数组（Fenwick Tree），也叫做树形数组，是一种支持单点修改、区间查询的数据结构。

这种数据结构可以在O(log n)的时间复杂度内实现单点修改和区间查询，相较于线段树，树状数组实现较为简单。

2 树状数组的实现原理树状数组的核心思想是利用二进制中的位运算来维护前缀区间和。

假设有一个数组a[]，其前缀和为sum[]，那么对于每个下标i，只需要维护[1,i]这个区间的和，即sum[i]。

这样，当需要查询区间[1,r]的和时，只需要计算sum[r]即可，不需要遍历每一个元素。

对于单点修改操作，假设我们要将数组a[]的第i个元素修改为x，我们只需要将第i个元素的值改为x，并且要将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中。

3 树状数组的实现细节3.1 树状数组的初始化树状数组需要初始化为0，因为我们需要维护的是每个元素的前缀和，如果没有初始化为0，其前缀和也就变得不可预测了。

查询区间[1,r]的和时，只需要计算sum[r]即可。

具体实现过程为：从r开始向前跳，每一个位置的前缀和都加到一个答案变量ans中，直到跳到0为止。

可以使用以下的代码实现：```C++int query(int x){int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans;}```修改操作也很简单，只需要将第i个位置的值改为x，然后将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中，可以使用以下的代码实现：```C++void update(int x, int val){while(x <= n){tree[x] += val;x += lowbit(x);}}```4 树状数组与线段树的比较相对于线段树，树状数组的实现更为简单，而且更加省空间。

数据结构之树状数组咱今天来聊聊数据结构里一个特别有趣的家伙——树状数组。

要说这树状数组啊，就像是我们生活中的小帮手，能帮我们解决好多看似复杂的问题。

我想起之前有一次，学校组织数学竞赛，其中有一道题可把好多同学都难住了。

题目是这样的：给定一个整数数组，要快速计算出某一段区间内数字的和。

当时好多同学都用最笨的办法，一个个数字去加，费了好大劲还容易出错。

这时候，树状数组就派上用场啦！它就像一个聪明的小管家，能快速又准确地算出我们想要的结果。

树状数组的原理其实不难理解。

想象一下，我们把数组里的数字看成是一棵棵小树苗，这些小树苗按照一定的规则排列成了一片小树林。

通过巧妙的设计，我们能快速找到想要的那一片小树苗的总和。

比如说，我们有一个数组 1, 3, 5, 7, 9 ，用树状数组来表示的话，就会有一番特别的构造。

它可不是简单地把数字罗列，而是通过一些巧妙的计算和存储方式，让我们在查找区间和的时候能够迅速得到答案。

树状数组的更新操作也挺有意思。

就好比我们在小树林里新种了一棵小树苗，或者给某一棵小树苗又长高了一些，我们得及时更新整个树林的状态，让它能准确反映出最新的情况。

而且，树状数组在解决实际问题的时候，那叫一个高效。

比如计算一个班级学生某一段时间内的考试成绩总和，或者统计一个月内某种商品的销售总量在不同时间段的情况。

再想想，如果把树状数组比作一个神奇的魔法盒子，我们输入一些数字，它就能按照特定的魔法规则，迅速给我们吐出我们想要的结果。

总之啊，树状数组虽然看起来有点神秘，但只要我们深入了解它，就会发现它其实特别有趣又实用。

就像我们在生活中，遇到各种难题，只要找到了合适的方法和工具，就能轻松解决。

希望大家都能跟树状数组成为好朋友，让它帮助我们在数据的世界里畅游，解决更多有趣的问题！。

树状数组武钢三中 吴豪【引言】在解题过程中，我们有时需要维护一个数组的前缀和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的最小幂即可。

树状数组习题（⼀本通）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//认真读题呀看给出数据的特征，是按照纵坐标从⼩到⼤排序的，纵坐标相同的是横坐标从⼩到⼤给出的//也就是说，我们可以不管纵坐标，按照它给出的横坐标依次插⼊，并统计当前星星之前的横坐标⼩于它的星星个数。

树状数组第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的位置其实从我画的满二叉树中就可以看出来。

树状数组的算法原理宝子！今天咱来唠唠树状数组这个超酷的东西。

树状数组啊，就像是一个魔法小助手，能帮我们快速解决好多关于数组的问题呢。

你想啊，要是有一个长长的数组，里面有好多好多数字，我们要对它做一些统计操作，比如说求某个区间的和之类的，要是用普通的方法，那可就太麻烦啦。

咱先说说树状数组的结构。

它看起来有点像一棵树，但又不是那种特别复杂的树。

它的每个节点都和数组里的元素有着神秘的联系。

你可以把它想象成是一群小精灵在守护着数组。

这些小精灵们可不是乱站的，它们有着自己独特的排列方式。

比如说，对于一个普通的数组，树状数组的节点是怎么对应的呢？树状数组的每个节点实际上是对应着原数组的一段区间。

这就很神奇啦，就好像每个小精灵都负责看守数组里的一块小天地。

而且呢，这些区间还有重叠的部分，就像小精灵们的地盘有时候会有交叉一样。

那它是怎么构建的呢？这就像是搭积木一样。

我们从最基础的元素开始，一点点地构建出这个树状结构。

最开始的时候，每个元素就像是一个小种子，然后随着构建的过程，它们慢慢组合起来，形成更大的节点。

这个过程其实并不复杂，只要按照一定的规则，就像按照一个小魔法咒语一样，就能轻松构建出来。

再说说它的查询操作。

这可是树状数组的拿手好戏。

当我们想要知道某个区间的和的时候，树状数组就像一个超级计算器一样，迅速给出答案。

它不是傻乎乎地一个一个数字去加哦，而是利用它的树状结构，巧妙地跳跃式计算。

就好比我们要找从第3个元素到第7个元素的和，树状数组不会从3加到7，而是根据它的节点关系，快速地找到对应的几个节点，把它们的值加起来就好啦。

这速度，就像闪电一样快。

还有更新操作呢。

如果我们改变了原数组里的一个元素的值，树状数组也能很快地做出调整。

它不会把整个树状结构都重新构建一遍，而是像一个聪明的小工匠，只对受到影响的部分进行修改。

这就像在一个大城堡里，有一块小砖头坏了，工匠只需要修补那一块，而不是把整个城堡都拆了重建。

树状数组在很多实际的问题里都特别有用。

Zjoi2017树状数组2.1 题⽬描述漆⿊的晚上，九条可怜躺在床上辗转反侧。

难以⼊眠的她想起了若⼲年前她的⼀次悲惨的 OI ⽐赛经历。

那是⼀道基础的树状数组题。

给出⼀个长度为 n 的数组 A，初始值都为 0，接下来进⾏ m 次操作，操作有两种：• 1 x，表⽰将 Ax 变成 (Ax + 1) mod 2。

• 2 l r，表⽰询问 ( ∑r i=l Ai) mod 2。

尽管那个时候的可怜⾮常的 simple，但是她还是发现这题可以⽤树状数组做。

当时⾮常 young 的她写了如下的算法：1: function Add(x)2: while x > 0 do3: Ax ← (Ax + 1) mod 24: x ← x − lowbit(x)5: end while6: end function7:8: function Find(x)9: if x == 0 then10: return 011: end if12: ans ← 013: while x ≤ n do14: ans ← (ans + Ax) mod 215: x ← x + lowbit(x)16: end while17: return ans18: end function19:20: function Query(l, r)21: ansl ← Find(l − 1)22: ansr ← Find(r)23: return (ansr − ansl + 2) mod 224: end function其中 lowbit(x) 表⽰数字 x 最վ的⾮ 0 ⼆进制位，例如 lowbit(5) = 1, lowbit(12) = 4。

进⾏第⼀类操作的时候就调⽤ Add(x)，第⼆类操作的时候答案就是 Query(l, r)。

如果你对树状数组⽐较熟悉，不难发现可怜把树状数组写错了：Add ， Find 中 x 变化的⽅向反了。

因此这个程序在最终测试时华丽的爆 0了。