TFcis 2016 summer: Data Structure

2016-lecture-data-structure.md

TFcis 2016 summer: Data Structure

Index

1. Segment Tree
2. BIT (Binary Indexed Tree)
3. Treap
4. Persistence Data Structure (Copy on write)

Segment Tree

RMQ: Range Maximum/Minimum Query
https://domen-blog.github.io/posts/2015-08-20/hoj-144/

Build: O(N)
Modify(單點修改): O(lg N)
Query(區間查詢): O(lg N)

lazy flag

區間修改: O(lg N)

BIT

某種精簡版的線段樹(?)

low bit

           100110
low bit: = 000010 (binary)

low bit of i = i&-i (-i 使用二的補數)

code

int bit[MAX_N+1];
int sum(int i)
{
	int s=0;
	while(i>0)
	{
		s+=bit[i];
		i-=i&-i; //low bit
	}
	return s;
}
void add(int i,int v)
{
	while(i<=n)
	{
		bit[i]+=v;
		i+=i&-i;
	}
}

Treap

• 二元搜尋樹 (Binary Search Tree)
• 二叉堆 (Binary Heap)

struture Treap {
	Treap *l, *r;
	int pri, key;
};

merge

10行

Treap *merge(Treap *a, Treap *b) {
	if (!a || !b) return a?a:b;
	if (a->pri > b->pri) {
		a->r = merge(a->r, b);
		return a;
	} else {
		b->l = merge(a, b->l);
		return b;
	}
}

又是10行

void split(Treap *t, Treap *&a, Treap *&b, int k) {
	if(!t) return a = b = nullptr;
	else if (t->key <= k) {
		a = t;
		split(t->r, a->r, b, k);
	} else {
		b = t;
		split(t->l, a, b->l, k);
	}
}

code - TOJ 263.cpp

Persistence Data Structure

copy on write

Practice

Segment Tree

Basic: HOJ 144 (壞了QQ), TIOJ 1603, POJ 3468(lazy flag), TIOJ 1871, HDU 1754, codeforces 52C
Advanced: ZJ a164, POJ 1823, TIOJ 1224, TOJ 242, TIOJ 1895, POJ 2155(二維), TIOJ 1887, TIOJ 1408, TIOJ 1161, TIOJ 1827, codechef QSET, codechef GCDQ

BIT

TOJ 11, TIOJ 1667, TIOJ 1272, TOJ 12, POJ 3067

Treap

Basic: TOJ 263, TIOJ 1305
Advanced: TOJ 242, TOJ 31, UVA 12538(持久化)

Other (以前學長整理的)

POJ 3580,3928,2352,2481,2029,3067,2777
HDU 1754,2795,1890,1394,1166
UVA 12538,11525,11992,12086,1406,11423,1232,11983,1400,12501,1513
TOJ 31

Treap - toj 263.cpp

#include <bits/stdc++.h>
#define INF 1001000000
using namespace std;
struct Treap;
Treap *nul;
struct Treap{
	int pri,val,sz;
	Treap *l,*r;
	int mx;
	Treap(int v)
	{
		mx=val=v;
		pri=rand();
		l=r=nul;
		sz=1;
	}
	void up()
	{
		sz=l->sz+r->sz+1;
		mx=max({val,l->mx,r->mx});
	}
	~Treap()
	{
		if(l!=nul) delete l;
		if(r!=nul) delete r;
	}
};
Treap *merge(Treap *a,Treap *b)
{
	if(a==nul) return b;
	if(b==nul) return a;
	if(a->pri>b->pri)
	{
		a->r=merge(a->r,b);
		a->up();
		return a;
	}
	else
	{
		b->l=merge(a,b->l);
		b->up();
		return b;
	}
}
void split(Treap *t,Treap *&a,Treap *&b,int k)
{
	if(t==nul) {a=b=nul; return;}
	if(k<=t->l->sz)
	{
		b=t;
		split(t->l,a,t->l,k);
	}
	else
	{
		a=t;
		split(t->r,t->r,b,k-t->l->sz-1);
	}
	t->up();
}
int a[100000];
Treap *build(int l,int r)
{
	if(l==r) return new Treap(a[l]);
	int mid=(l+r)/2;
	return merge(build(l,mid),build(mid+1,r));
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	// srand(829);
	srand(time(0));

	nul=new Treap(-INF);
	nul->sz=0;

	int n,q;
	Treap *tr;
	while(cin>>n>>q)
	{
		for(int i=0;i<n;i++)
			cin>>a[i];
		tr=build(0,n-1); //faster
		// tr=nul;
		// for(int i=0;i<n;i++)
		// {
		// 	int t;
		// 	cin>>t;
		// 	tr=merge(tr,new Treap(t));
		// }
		while(q--)
		{
			int type,x,y;
			cin>>type;
			if(type==1)
			{
				cin>>x>>y;
				Treap *a,*b,*c;
				split(tr,a,b,x-1);
				split(b,b,c,1);
				delete b;
				b=new Treap(y);
				tr=merge(merge(a,b),c);
			}
			else if(type==2)
			{
				cin>>x>>y;
				Treap *a,*b,*c;
				split(tr,a,c,y);
				split(a,a,b,x-1);
				cout<<b->mx<<endl;
				tr=merge(merge(a,b),c);
			}
			else if(type==3)
			{
				cin>>x>>y;
				Treap *a,*b,*c;
				split(tr,a,c,x-1);
				b=new Treap(y);
				tr=merge(merge(a,b),c);
			}
			else
			{
				cin>>x;
				Treap *a,*b,*c;
				split(tr,a,b,x-1);
				split(b,b,c,1);
				delete b;
				tr=merge(a,c);
			}
		}
		delete tr;
	}
}