线段树的一种简单实现

发现之前没有整理过线段树的代码，填一下坑。

int Array[maxn];

class SegmentTree{
  public:
  SegmentTree* BuildTree(const int L,const int R){
    SegmentTree *Node=new SegmentTree;
    Node->l=L,Node->r=R;
    Node->Tag=0;
    if(L==R){
      Node->LeftSon=Node->RightSon=nullptr;
      Node->Sum=Array[L];
    }else{
      int Mid=(L+R)>>1;
      Node->LeftSon=BuildTree(L,Mid);
      Node->RightSon=BuildTree(Mid+1,R);
      Node->Update();
    }
    return Node;
  }

  inline bool InRange(const int L,const int R){
    return (L<=l)&&(r<=R);
  }

  inline bool OutOfRange(const int L,const int R){
    return (R<l)||(r<L);
  }

  inline void MakeTag(const int Add){
    Tag+=Add;
    Sum+=(r-l+1)*Add;
  }

  inline void PushDown(){
    if(Tag){
      LeftSon->MakeTag(Tag);
      RightSon->MakeTag(Tag);
      Tag=0;
    }
  }

  inline void Update(){
    Sum=LeftSon->Sum+RightSon->Sum;
  }

  void Modify(const int L,const int R,const int Add){
    if(InRange(L,R)) MakeTag(Add);
    else if(!OutOfRange(L,R)){
      PushDown();
      LeftSon->Modify(L,R,Add);
      RightSon->Modify(L,R,Add);
      Update();
    }
  }

  int GetSum(const int L,const int R){
    if(InRange(L,R)) return Sum;
    if(OutOfRange(L,R)) return 0;
    PushDown();
    return LeftSon->GetSum(L,R)+RightSon->GetSum(L,R);
  }

  private:
  int l,r;
  int Sum,Tag;
  SegmentTree *LeftSon,*RightSon;
}*Root;

/*
在主函数中 Root=Root->BuildTree(L,R);
*/