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