20131023: 线段树，划分树；云存储；windows管理员权限；修改host
喜讯！！频繁搜索的大作业推迟了，而且第三个大作业取消了！~~爽歪歪~~~~~
今天主要是在研究（其实是在学习）高级数据结构中的线段树， 树状数组和树堆这三个， 这也是我们数算实习课要求的，大致的都已经看了一遍， 树堆应该就是用平衡二叉搜索树来优化搜索插入查询，时间复杂度均未lgn， 但是还没用过！~~
树状数组已经干掉一道了，大致了解了用法和用途，但是第二道统计排序算法的交换次数还没有什么好的想法， 打算明天两道树状数组的一起写个总结吧！~
今天主要是成功干掉两道线段树， 不是很简单啊（还是参考了下别人的代码， 因为实在是没用过）， 只要掌握关于线段树的构造与查询与更新就基本没有问题， 值得一提的是，
我们没有必要每做一个改变就马上更新全部， 事实上这样是很容易超时的， 为了节约时间， 我们只做必要的操作， 也就是只做必要的更新， 要用时或者必须更新时才更新， 其中必须更新是指你再不更新会造成数据的错误！~
两道都是poj上的题， 第一道的代码如下， 我的习惯是很多思想都直接在代码中写出， 边看边读边想很有效率！~
/*
Name: A Simple Problem with Integers
Copyright: from openjudge
Author: xiaoli
Date: 22/10/13 11:49
Description: 线段树入门， 关于线段树的建立， 查询与更新
*/
#include<iostream>
using namespace std;
struct point
{
int l;
int r;
long long add,sum; //add用于记录增加量， 也可作为标记
}dot[300002]; //n的范围是100000， 但总的节点数要大很多， 否则runtime error
int v[100002]={0};
//创建满二叉树
void create(int l, int r, int pos)
{
dot[pos].l=l;
dot[pos].r=r;
dot[pos].add=0;
if(l==r) //叶节点
{
cin>>dot[pos].sum;
return;
}
int mid=(l+r)>>1;
create(l, mid,pos*2); //节点的编号规律
create(mid+1, r, pos*2+1);
dot[pos].sum=dot[pos*2].sum+dot[pos*2+1].sum;
}
//为了简化，先记录， 需要时再更新！！！---只做有用的操作!
void update(int l, int r, int pos, int add)
{
if(l<=dot[pos].l&&r>=dot[pos].r) //包含节点对应的线段
{
dot[pos].add+=add; //为其子节点做记录
dot[pos].sum+=(dot[pos].r-dot[pos].l+1)*add; //更新当前节点的和值
return;
}
if(dot[pos].add) //更新其所有子节点以保证后面求和正确
{
dot[pos*2].add+=dot[pos].add;
dot[pos*2+1].add+=dot[pos].add;
dot[pos*2].sum+=(dot[pos*2].r-dot[pos*2].l+1)*dot[pos].add;
dot[pos*2+1].sum+=(dot[pos*2+1].r-dot[pos*2+1].l+1)*dot[pos].add;
dot[pos].add=0;
}
if(r>=dot[pos*2+1].l)
update(l, r, pos*2+1, add);
if(l<=dot[pos*2].r)
update(l,r, pos*2, add);
dot[pos].sum=dot[pos*2].sum+dot[pos*2+1].sum;
}
long long query(int l, int r, int pos)
{
if(l==dot[pos].l&&r==dot[pos].r)
return dot[pos].sum;
int mid=(dot[pos].l+dot[pos].r)>>1;
//同样需要更新其所有子节点
if(dot[pos].add)
{
dot[pos*2].add+=dot[pos].add;
dot[pos*2+1].add+=dot[pos].add;
dot[pos*2].sum+=(dot[pos*2].r-dot[pos*2].l+1)*dot[pos].add;
dot[pos*2+1].sum+=(dot[pos*2+1].r-dot[pos*2+1].l+1)*dot[pos].add;
dot[pos].add=0;
}
//分三种情况讨论
if(l>mid)
return query(l,r, pos*2+1);
else if(r<=mid)
return query(l,r,pos*2);
else //与两个子节点都有交集
return query(l,mid,pos*2)+query(mid+1,r,pos*2+1);
}
int main()
{
int n,m;
cin>>n>>m;
create(1, n, 1);
int i,j,k;
char c;
while(m--)
{
cin>>c;
if(c=='C')
{
cin>>i>>j>>k;
update(i,j,1, k);
}
else if(c='Q')
{
cin>>i>>j;
cout<<query(i,j,1)<<endl;
}
}
return 0;
}
这一道只是入门题， 只要掌握基本操作和只在必要时进行更新基本上就没有问题， 注意每次更新后对应节点的add=0， 也就标志着不要重复更新，否则很浪费时间！~
第二道题需要在线段树的基础上改进一下结构， 做法很多种， 划分树， 归并排序线段树， 主席树， 我用的是划分树， 对其他两种还不清楚！~
大意是在一个数组中选定一个区间求k-th的值， 暴力搜索必然超时， 注意到主要是避免重复运算， 而线段树是对区间问题一个很好的优化！~
现在的问题是如何用线段树， 划分树的思想是把当前节点的区间中排序后二分放置， 但是在左右子树中的数是按原来数组的顺序排的， 输入数组后按这个原则建树， 建树过程中有需要记录的东西（主要是方便后面查询）， 自己建树后查询时就会感觉到需要记录啥！~
细节处理和大致思想和注意问题程序中都写的很清楚：
/*
Name: K-th Number
Copyright: from poj
Author: xiaoli
Date: 22/10/13 16:02
Description:
问题：给一串数字， 多次询问某段区间的第k小值
1.线段树的拓展划分树， 另外，好像有一种叫做归并排序线段树的结构也可以用来解决此类问题
2.主席树：作为拓展代码摘录在后部
*/
#include<iostream>
#include<cstdio>
#include<cstdlib> //排序时尽量选择sort，不准用STL就用qsort
using namespace std;
#define MAX 100005 //推荐的常量表达方式, 最大个数
#define H 20 //最大深度
int a[MAX]={0}; //记录排序后的数组
int sum[H][MAX]={0}; //记录每次建立子树时该段区间转移到左子树的个数
int tree[H][MAX]={0}; //记录每一层的序列情况， 方便查找
int cmp(const void*p1,const void*p2) //须牢记qsort的比较函数形式
{
return *(int*)p1-*(int*)p2; //返回-1是<， 按<排序
}
//不使用结构体而是采取传参的方式建树， 记录有用的信息即可
void build(int l, int r, int depth)
{ //数量上严格二分， 遇到相等的情况也要保证数量的对应！
int mid=(l+r)>>1;
int i,lcnt=l,rcnt=mid+1,j;
int sum_mid=mid-l+1; //确定等于mid的个数
for(i=mid-1;i>=l;--i)
if(a[i]<a[mid])
{
sum_mid=mid-i;
break;
}
for(i=l;i<=r;++i)
{
if(i==l) //确定l到i这段区间转移的个数
sum[depth][i]=0;
else
sum[depth][i]=sum[depth][i-1];
if(tree[depth][i]<a[mid])
{
sum[depth][i]++;
tree[depth+1][lcnt++]=tree[depth][i];
}
else if(tree[depth][i]==a[mid]&&sum_mid) //左范围内的相等值埋入左子树
{
sum_mid--;
sum[depth][i]++;
tree[depth+1][lcnt++]=tree[depth][i];
}
else //右范围的相等或大于
{
//注意sum统计的是左子树
tree[depth+1][rcnt++]=tree[depth][i];
}
}
if(l==r) return; //已到叶节点
build(l,mid,depth+1);
build(mid+1,r,depth+1);
}
int query(int l1, int r1, int l2, int r2, int k, int depth)
{
if(l1==r1) return tree[depth][l1];
//判断往左右哪个方向去查询
int sum1=0,sum2=0,mid=(l1+r1)>>1;
if(l2!=l1) //相等意味着0
sum1=sum[depth][l2-1];
sum2=sum[depth][r2]-sum1; //相减即得l2到r2这段区间的转移个数
//查找范围也得更新！！！(在子树中的由l2-r2加入的范围才是我们的搜索区间，前面的不是！！！）
//并且注意该范围不一定是排好序的，所以不能缩小!
if(sum2>=k) //往左子树查询
return query(l1,mid, l1+sum1,l1+sum1+sum2-1,k,depth+1);
else
{
int len=r2-l2+1;
len-=sum2; //计算加入右子树的个数
int t1=mid+1+l2-l1-sum1; //l2-l1-sum1是l1之前加入右子树的
int t2=t1+len-1;
return query(mid+1,r1,t1,t2,k-sum2,depth+1);
}
}
int main()
{
int n,m,i,j,k;
scanf("%d %d",&n,&m);
for(i=1;i<=n;++i) //注意存储范围是1-n
{
scanf("%d",&a[i]);
tree[0][i]=a[i];
}
/*
for(i=n;i>1;--i)
for(j=1;j<i;++j)
if(a[j]>a[j+1])
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
*/
qsort(a+1,n,sizeof(int),cmp); //注意指针指向要正确
build(1,n,0); //建立树形结构
while(m--)
{
scanf("%d %d %d",&i,&j,&k); //scanf 显著快于 cin，当有大量输入时必用！！！
int ans=query(1,n,i,j,k,0);
printf("%d\n",ans);
}
return 0;
}
/*
题目大意：给一串数字，多次询问区间的第k小值
思路：不带修改的主席树
附资料：http://blog.csdn.net/metalseed/article/details/8045038
http://www.abandonzhang.com/archives/29
——————————————————————————————————————————————————————————————————————————————————————————————
以下转自http://prominences.weebly.com/1/post/2013/02/1.html
可持久化线段树，也叫作函数式线段树，也就是主席树，（。。。因为先驱就是fotile主席。。Orz。。。）
网上的教程很少啊，有的教程写得特别简单，4行中文，然后就是一篇代码～～
这里，我将从查找区间第k小值（不带修改）题的可持久化线段树做法中，讲一讲主席树。
只是略懂，若有错误，还请多多包涵！
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。/*找不到比较科学的定义，就拿这个凑凑数吧～～～
这个数据结构很坑啊，我研究了一整天才差不多理解了一些（。。太笨了。。。）。所以，要理解好每一个域或变量的意义。
开讲！
一些数据结构，比如线段树或平衡树，他们一般是要么维护每个元素在原序列中的排列顺序，要么是维护每个元素的大小顺序，若是像二者兼得。。（反正我是觉得很。。）那么，这道题就想想主席树吧～/*还可以用划分树做
开讲！～好像说过一边了
既然叫“函数式线段树”，那么就应该有跟普通线段树相同的地方。一颗线段树，只能维护一段区间里的元素。但是，每个询问的区间都不一样，若是对每段区间都单独建立的线段树，那～萎定了～。因此，就要想，如何在少建，或建得快的情况下，能利用一些方法，得出某个区间里的情况。
比如一棵线段树，记为tree[i][j]，表示区间[i,j]的线段树。那么，要得到它的情况，可以利用另外两棵树，tree[1][i-1]和tree[1][j]，得出来。也就是说，可以由建树的一系列历史版本推出。
那么，怎么创建这些树呢？
首先，离散化数据。因为如果数据太大的话，线段树会爆～～
在所有树中，是按照当前区间元素的离散值（也就是用大小排序）储存的，在每个节点，存的是这个区间每个元素出现的次数之和（data域）。出现的次数，也就是存了多少数进来（建树时，是一个数一个数地存进来的）。
先建议棵线段树，所有的节点data域为0。再一个节点一个节点地添加。把每个数按照自己的离散值，放到树中合适的位置，然后data域+1，回溯的时候也要+1。当然，不能放到那棵空树中，要重新建树。第i棵树存的是区间（原序列）[1,i]。但是，如果是这样，那么会MLE+TLE。因此，要充分利用历史版本。用两个指针，分指当前空树和前一棵树。因为每棵树的结构是一样的，只是里面的data域不同，但是两棵相邻的树，只有一数只差，因此，如果元素要进左子树的话，右子树就会跟上个树这个区间的右子树是完全一样的，因此，可以直接将本树本节点的右子树指针接到上棵树当前节点的右儿子，这样即省时间，又省空间。
每添加一个节点（也就是新建一棵树）的复杂度是O(logn)，因此，这一步的复杂度是O(nlogn)。
建完之后，要怎么查找呢？
跟一般的，在整棵树中找第k个数是一样的。如果一个节点的左权值（左子树上点的数量之和）大于k，那么就到左子树查找，否则到右子树查找。其实主席树是一样的。对于任意两棵树（分别存区间[1,i]和区间[1,j] i<j），在同一节点上（两节点所表示的区间相同），data域之差表示的是，原序列区间[i,j]在当前节点所表示的区间里，出现多少次（有多少数的大小是在这个区间里的）。同理，对于同一节点，如果在两棵树中，它们的左权值之差大于等于k，那么要求的数就在左孩子，否则在右孩子。当定位到叶子节点时，就可以输出了。
——————————————————————————————————————————————————————————————————————————————————————————————
鄙人的一些理解：所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。
代码（最原始的树所有结点的值都为0，就算建好一棵树了……）：
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
struct Node {
int L, R, sum;
};
Node T[MAXN * 20];
int T_cnt;
void insert(int &num, int &x, int L, int R) {
T[T_cnt++] = T[x]; x = T_cnt - 1;
++T[x].sum;
if(L == R) return ;
int mid = (L + R) >> 1;
if(num <= mid) insert(num, T[x].L, L, mid);
else insert(num, T[x].R, mid + 1, R);
}
int query(int i, int j, int k, int L, int R) {
if(L == R) return L;
int t = T[T[j].L].sum - T[T[i].L].sum;
int mid = (R + L) >> 1;
if(k <= t) return query(T[i].L, T[j].L, k, L, mid);
else return query(T[i].R, T[j].R, k - t, mid + 1, R);
}
struct A {
int x, idx;
bool operator < (const A &rhs) const {
return x < rhs.x;
}
};
A a[MAXN];
int rank[MAXN], root[MAXN];
int n, m;
int main() {
T[0].L = T[0].R = T[0].sum = 0;
root[0] = 0;
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i].x);
a[i].idx = i;
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) rank[a[i].idx] = i;
T_cnt = 1;
for(int i = 1; i <= n; ++i) {
root[i] = root[i - 1];
insert(rank[i], root[i], 1, n);
}
while(m--) {
int i, j, k;
scanf("%d%d%d", &i, &j, &k);
printf("%d\n", a[query(root[i - 1], root[j], k, 1, n)].x);
}
}
}
*/
最后一部分是主席树的思想， 我自己也还没看， 权当收藏与分享了！~~
算法部分告一段落了， 今天还学习了一些软件知识， 关于windows管理员权限的获得， 修改host文件以打开访问等等。
一般程序和文件直接点右键就有管理员身份选项， 对于系统里面的一些文件修改后可能需要管理员权限才能保存， 这时候就要以管理员身份登录， winwows默认是不提供管理员登录选项的， 这也是为了保证你的电脑安全， 但是这样搞的好像在自己的电脑面前自己就是个外人， 而且确实有些操作无法实现， 不满足的朋友还是必须取得最高统治权的！~直接进入计算机管理选择用户->administrator->属性， 去掉禁用之前的勾勾即可！~ 选择注销或者切换用户， 登录界面就会出现管理员选项（可以自己取名，初次无密码！）， 这里注意不同用户可以共享计算机资料（除非某些规定了用户权限的）， 也就是 说资料都是一样的， 但是软件的设置安装基本上是完全独立的！！~~
需要修改host主要是因为一些网站被禁用， 比如连不上google driver的下载服务器， 进入c->windows->system32->drivers->etc->host，修改即可（需要管理员身份运行才能保存！）
PS：我修改了， 但还是没连上， 不知道为啥~~
关于云存储， 今天详细了解了下， 主要就是方便同步， 功能其实很清晰， 但选择却很难， 因为现在云存储服务太多了， 特别大的有dropbox, google drive,, skydrive， 他们各自都有提供的免费扩容的活动， 需要自己加以关注， 其中skydrive与office搭配非常好（都是微软的）， 其他的当然搭配起来就有一些问题， dropbox可以在各种操作系统下安装客户端登陆， 但其他两个不能在linux下（现在天朝把dropbox给禁了~~）
现在最开始提供的免费容量差不多， google drive提供的已经提高到15G，应该说是很不错的， 另外google一向追求全面发展， 后面必然也会开发出linux下的driver, 而与dropbox相比， google的上传速度远远胜之， 但是云存储的功能方面还不是特别细致， 比如上传重复文件却不加检验， dropbox下是没有这个问题的； skydrive好像中国用户用起来会有一些问题， 至少我的office登录从来没连上过， 果断放弃！~所以最后选择了google drive， 希望google能做出更大的改进！~（google drive还提供了分享权限的设置， 这是其他没有的功能！~）
另外推荐一下国内的云存储平台（或许不能这么叫 ，但功能差不多）， 新浪的微盘海水很不错的， 很轻松的扩容任务， 很好看的界面， 更让我喜欢的是可以直接把新浪爱问共享平台中的文件保存到微盘， 无需消耗积分， 喜欢看电子书的朋友， 爽爆了！！！~~~这种神器我到今天才发现， 抓狂有木有！~~~
goodnignt!~