HDU 1541.Stars-一维树状数组(详解)

摘要:
这位前辈很久以前说过的树形数组最近受到了关注,enmmmm…树形数组是一种具有日志查询和修改复杂性的数据结构。相比之下,树数组的效率要高得多。以栗子7为例,求出前七个数的和,即s+=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7];因为1-->001C1=A12-->010C2=A1+A23-->011C3=A34-->100C4=A1+A2+A3+A45-->101C5=A56-->110C6=A5+A67-->111C7=A78-->1000C8=A1+A3+A4+A5+A6+A7+A8,所以它是C[4]+C[6]+C[7];C[100]+C[110]+C[111];第一个s+=c[7];那么低位[7]=&=001;此时,i=7,因此7低位=111-001=110110为6;s+=c[6];低位=&=010;此时,i=6,所以6低位=110-010=100100是4;s+=c[4];低位=&=100;此时,i=4,所以它是4低位=100-100=0。

树状数组,学长很早之前讲过,最近才重视起来,enmmmm。。。

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

树状数组和线段树很像,但能用树状数组解决的问题,基本上都能用线段树解决,而线段树能解决的树状数组不一定能解决。相比较而言,树状数组效率要高很多。

HDU 1541.Stars-一维树状数组(详解)第1张

观察这个图ヾ(◍°∇°◍)ノ゙
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = 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
感觉很神奇,是怎么做到这样的呢。
哈,全靠二进制
将数组的节点序号都转化成二进制。
就是这样的:
1--->001 C1 = A1
2--->010 C2 = A1 + A2
3--->011 C3 = A3
4--->100 C4 = A1 + A2 + A3 + A4
5--->101 C5 = A5
6--->110 C6 = A5 + A6
7--->111 C7 = A7
8--->1000C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
但是这又有什么关系呢?!!!∑(゚Д゚ノ)ノ
度娘说了:
这里有一个有趣的性质:
设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,
所以很明显:Cn = A(n – 2^k + 1) + A(n-2^k+2)+... + An
什么意思呢?举个栗子,1对应的二进制是001,二进制末尾0的个数为0,所以k=0,
所以C1=A(1-2^k+1)+...An 就是C1=A(1-2^0+1)=A(1);
再来个栗子,4对应的二进制是100,二进制末尾0的个数为2,所以k=2,
所以C4=A(4-2^2+1)+A(4-2^2+2)+...+A(4)=A(1)+A(2)+A(3)+A(4);
再搞不懂就自己再手推几个数试试就可以了。
至于怎么得出来的这个神奇的东西,就是靠二进制啦。总结出来这个式子的人好厉害((✧◡✧))
接下来就是怎么代码实现这个呢?
就是要靠神奇的lowbit了。
int lowbit(intx)
{
return x&(-x); }

x&(-x)就是整数x与其相反数(负号取反)的按位与:相同位的两个数字都为1,则为1;若有一个不为1,则为0,即:1&1=1,0&1=0,0&0=0;

计算机中负数使用对应正数的补码来表示。

-x就是x对应的二进制数先各位取反,0变成1,1变成0。然后最低位加1。

举个栗子,4对应二进制为100;-4对应的为011+1=100,所以为(100)&(100)所以为100。

知道这个又能干嘛呀,就可以进行区间查询啦。

区间查询利用C[i]求A数组前i个的和;

//代码1:
int SUM(intn)
{
int s=0; while(n>0){ s+=c[n]; n-=lowbit(n); } returns; }
//代码2:
int SUM(intn)
{
int s=0; for(int i=n;i>0;i-=lowbit(i)) s+=c[i]; returns; }

两个代码哪个好理解理解哪个。

接着刚刚举的栗子4,求A数组前4个数的和;

lowbit(4)得出100;然后100就是4,所以为s+=c[4];此时i=4,4-lowbit(4)=100-100=0;结束。

再举个栗子7,求前7个数的和,就是s+=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7];

因为

1--->001 C1 = A1
2--->010 C2 = A1 + A2
3--->011 C3 = A3
4--->100 C4 = A1 + A2 + A3 + A4
5--->101 C5 = A5
6--->110 C6 = A5 + A6
7--->111 C7 = A7
8--->1000C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
所以为C[4]+C[6]+C[7];
就是C[100]+C[110]+C[111];
首先s+=c[7];
然后lowbit[7]=(111)&(001)=001;此时i=7,所以为7-lowbit(7)=111-001=110,110就是6;s+=c[6];
lowbit(6)=(110)&(010)=010;此时i=6,所以为6-lowbit(6)=110-010=100,100就是4;s+=c[4];
lowbit(4)=(100)&(100)=100;此时i=4,所以为4-lowbit(4)=100-100=0,结束。
所以得到A数组中前7个数的和为C[7]+C[6]+C[4];
不懂的话再自己手推一个数就差不多懂了。
接下来就是单点更新
单点更新要从下往上依次更新。
//代码1:
void add(intx)
{
while(x<=N){ ++a[x]; x+=lowbit(x); } }
//代码2:
void add(int x,inty)
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y; }

更新过程仔细想一想就是查询过程的逆过程;

举个栗子,更新A1,还要继续更新C[1],C[2],C[4],C[8];

就是C[001],C[010],C[100],C[1000];

i=1;C[1]+=A[1];

lowbit(1)=(001)&(001)=001;此时i=1,所以为1+lowbit(1)=001+001=010,010就是2;C[2]+=A[1];

lowbit(2)=(010)&(110)=010;此时i=2,所以为2+lowbit(2)=010+010=100,100就是4;C[4]+=A[1];

lowbit(4)=(100)&(100)=100;此时i=4,所以为4+lowbit(4)=100+100=1000,1000就是8;C[8]+=A[1];结束。

好了,理解了树状数组就开始贴代码了。(;´д`)ゞ

HDU1541-Stars

Stars

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10611Accepted Submission(s): 4240

Problem Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
HDU 1541.Stars-一维树状数组(详解)第2张
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
0
代码:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<bitset>
6 #include<cassert>
7 #include<cctype>
8 #include<cmath>
9 #include<cstdlib>
10 #include<ctime>
11 #include<deque>
12 #include<iomanip>
13 #include<list>
14 #include<map>
15 #include<queue>
16 #include<set>
17 #include<stack>
18 #include<vector>
19 using namespacestd;
20 typedef long longll;
21 
22 const double PI=acos(-1.0);
23 const double eps=1e-6;
24 const ll mod=1e9+7;
25 const int inf=0x3f3f3f3f;
26 const int maxn=1e5+10;
27 const int maxm=100+10;
28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
29 
30 
31 inta[maxn],ans[maxn];
32 
33 int lowbit(intx)
34 {
35     return x&(-x);
36 }
37 
38 int getsum(intn)
39 {
40     int ans=0;
41     for(int i=n;i>0;i-=lowbit(i))
42         ans+=a[i];
43     returnans;
44 }
45 
46 void add(intx)
47 {
48     for(int i=x;i<=maxn;i+=lowbit(i))
49         ++a[i];
50 }
51 
52 intmain(){
53     intn,x,y;
54     while(~scanf("%d",&n)){
55         memset(a,0,sizeof(a));
56         memset(ans,0,sizeof(ans));
57         for(int i=0;i<n;i++){
58             scanf("%d%d",&x,&y);
59             x++;
60             ans[getsum(x)]++;
61 add(x);
62 }
63         for(int i=0;i<n;i++)
64             printf("%d
",ans[i]);
65 }
66     return 0;
67 }

溜了溜了。。。

免责声明:文章转载自《HDU 1541.Stars-一维树状数组(详解)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇谈谈我对百度广告管家的一些看法TIOBE 四月世界编程语言排行榜:C语言重回榜首下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

最长递增子序列

问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8},长度为4. 解法1:最长公共子序列法 这个问题可以转换为最长公共子序列问题。如例子中的数组A{5,6, 7, 1, 2, 8},则我们排序该数组得到数组A...

java 用JNA调用dll 参考文档

1Java调用C语言动态库(JNA方式):回调函数、结构体数组传参、结构体数组返回 2jna结构体数组JNA结构体数组 3JNA调用C语言动态链接库学习实践总结 4Java 通过 JNA 调用 DLL 返回 char * 字符串乱码问题的解决 5jna对结构体、指针、引用、拷贝参数传递的使用 6jna模拟指针开辟空间,数组首地址获取值 7JNA结构体参数传...

Java动手实验及课后程序

课后作业 一、编写程序,消息框显示计算结果 设计思想:导入Scanner包,使用JOptionPane类来实现消息框的输入和结果的显示。 程序代码: package com; import java.util.Scanner; //导入Scanner包 import javax.swing.JOptionPane; public class Manner ...

HDOJ 1166 敌兵布阵树状数组 线段树

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18120Accepted Submission(s): 7877 Problem Description C国的死对头A国这段时间正在进行军事演习...

php Array

1. 创建数组 创建一个包含指定范围的数组   array range( mixed low, mixed high [, number step]); 基于变量创建一个数组   array compact( mixed varname [, mixed…]);   extract(array &array) 将数组解析为变量 2. 计算数组大小...

LeetCode刷题笔记(3)Java位运算符与使用按位异或(进制之间的转换)

  1.问题描述   给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。   算法应该具有线性时间复杂度并且不使用额外空间。 输入: [4,1,2,1,2] 输出: 4   2.解题思路   这道题的主要的难点是具有线性时间复杂度并且不能使用额外的空间,因此就排除了很多的方法。   当时使用双指针尝试了以...