之前因为什么奇怪的原因抱回来一本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
