davidwang's Blog

之前因为什么奇怪的原因抱回来一本C++ Primer，认真研读之后发现什么都没看懂

但是唯一明白的就是我之前一直不会写C++啊。

然后大致草草的明白了类和继承和OOP编程的基础开始学习模板

写了各线段树的模板…… 区间修改的借口还待调试

#ifndef SEGMENT_TREE
#define SEGMENT_TREE

//这是一个我想使用的标准线段书模板
//我们需要提供节点类型，每个节点类型都必须包含push_down,push_up，两种操作
//如果使用函数的modify string 命令接口那么必须包含modify(std::string &)接口
//如果不想要使用这个接口，可以使用#define NOSTRINGMODIFY 来避免这个借口带来的编译问题
//其中modify可以接受一个字符串作为目的的操作
//这里我们提供一种标准的 class StandardNode 可以从中继承使用
#include <string>
#include <cmath>
const int DEFUALTSEGMENTSIZE = 100000;
template <typename T>
class SegmentTree{
public:
	explicit SegmentTree(int Size);
	explicit SegmentTree(T *,int Size);
	~SegmentTree();
	void init(T *);
	void modify(int pos,const T &x);
#ifndef NOSTRINGMODIFY
	void modify(int l,int r,const std::string &cmd);
	void modify(int l,int r,const std::string &cmd,const T &x);
#endif
	T query(int l,int r);
private:
	int Size;
	void build(int i,int l,int r,T *);
	void build(int i,int l,int r);
	void modify(int i,int pos,const T &x);
#ifndef UNFINSHIED
	void modify(int i,int l,int r,const std::string &cmd);
	void modify(int i,int l,int r,const std::string &cmd,const T &x);
	inline void push_up(int i);
	inline void push_down(int i);
#endif
	T query(int i,int l,int r);
	int D;
	class segmentTreeNodeClass{
	public:
		T data;
		int l,r;
		int mid(){ return l+r>>1; }
	}*s;
};

template<typename T>
SegmentTree<T>::SegmentTree(int _Size):Size(_Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D);
}

template<typename T>
SegmentTree<T>::SegmentTree(T *x,int Size):Size(Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D,x);
}

template<typename T>
SegmentTree<T>::~SegmentTree(){
//currently do nothing at all
}	

template<typename T>
void SegmentTree<T>::init(T *x){
	build(1,1,1<<D,x);
}

template<typename T>
void SegmentTree<T>::modify(int pos,const T &x){
	modify(1,pos,x);
}
#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd){
	modify(1,l,r,cmd);
}

template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd,const T &x){
	modify(1,l,r,cmd,x);
}
#endif

template<typename T>
T SegmentTree<T>::query(int l,int r){
	return query(1,l,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r) return;
	int m = l+r>>1;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r,T *x){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r){
		if (l <= Size) s[i].data = x[l];
		s[i].data.setRange(l,r);
		return;
	}
	int m = l+r>>1;
	build(i<<1,l,m,x);
	build(i<<1|1,m+1,r,x);
	push_up(i);
	return;
}

template<typename T>
void SegmentTree<T>::modify(int i,int pos,const T &x){
	if (s[i].l==pos && s[i].r==pos){
		s[i].data = x;
		s[i].data.setRange(pos,pos);
		return;
	}
	push_down(i);
	if (pos <= s[i].mid()) modify(i<<1,pos,x);
	else modify(i<<1|1,pos,x);
	push_up(i);
}

#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd);
	else if (l>m) modify(i<<1|1,l,r,cmd);
	else modify(i<<1,l,m,cmd),modify(i<<1,m+1,r,cmd);
	push_up(i);
}


template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd,const T &x){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd,x);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd,x);
	else if (l>m) modify(i<<1|1,l,r,cmd,x);
	else modify(i<<1,l,m,cmd,x),modify(i<<1,m+1,r,cmd,x);
	push_up(i);
}
#endif

template<typename T>
T SegmentTree<T>::query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r) return s[i].data;
	int m=s[i].mid();
	T ret;
	push_down(i);
	if (r<=m) ret = query(i<<1,l,r);
	else if (l>m) ret =query(i<<1|1,l,r);
	else ret.push_up(query(i<<1,l,m),query(i<<1|1,m+1,r));
	push_up(i);
	return ret;
}

template<typename T>
inline void SegmentTree<T>::push_up(int i){
	s[i].data.push_up(s[i<<1].data,s[i<<1|1].data);
}

template<typename T>
inline void SegmentTree<T>::push_down(int i){
	s[i].data.push_down(s[i<<1].data,s[i<<1|1].data);
}

class StandardNode{
public:
	virtual void push_up(const StandardNode &x,const StandardNode &y)  {}
	virtual void push_down(StandardNode &x,StandardNode &y)  {}
	virtual void modify(const std::string &cmd)  {}
	virtual void modify(const std::string &cmd,const StandardNode &x)  {}
	virtual void setRange(int l,int r){}	
	virtual ~StandardNode(){}
};
#endif