树状数组 ST表 线性数据

单点修改，区间查询

区间修改，单点查询

线段树：树形结构

区间修改，区间查询

完全二叉树标记关系：

1为根，当前节点x，左子2x，右子2x+1.

0为根，当前节点x，左子2x+1，右子2x+2.

#include <iostream>

using namespace std;

int n,m,c,l,r,k;

int a[10050];//线性数组

int t[20050];//按照完全二叉树存 本质是平衡二叉树

int tag[20050];//惰性标记

//构造线段树

void buildTree(int fat,int left,int right){

   //当前节点下标fat，当前节点代表的数据范围left～right

   if(left==right){

       t[fat]=a[left];

       return ;

   }

   int mid=(left+right)>>1;

   buildTree(fat<<1,left,mid);//x<<1 = 2x

   buildTree(fat<<1|1,mid+1,right);//x<<1|1 = 2x+1

   t[fat]=t[fat<<1]+t[fat<<1|1];

}

//惰性标记：利用惰性标记推动修改或查询

//推动标记

void push_tag(int left,int right,int fat){

   int mid=(left+right)>>1;

   t[fat<<1]+=tag[fat]*(mid-left+1);

   t[fat<<1|1]+=tag[fat]*(right-mid);

   tag[fat<<1]=tag[fat];

   tag[fat<<1|1]=tag[fat];

   tag[fat]=0;

}

//区间更改

void update(int l,int r,int left,int right,int fat,int k){

   if(l<=left&&r>=right){

       t[fat]+=k*(right-left+1);

       tag[fat]+=k;

       return ;

   }

   push_tag(left,right,fat);

   int mid=(left+right)>>1;

   if(l<=mid) update(l,r,left,mid,fat<<1,k);

   if(r>mid) update(l,r,mid+1,right,fat<<1|1,k);

   t[fat]=t[fat<<1]+t[fat<<1|1];

}

//区间查询

int query(int l,int r,int left,int right,int fat){

   //要查的范围（目标），和正在查的范围

   int ans=0;

   if(l<=left&&r>=right) return t[fat];

   push_tag(left,right,fat);

   int mid=(left+right)>>1;

   if(l<=mid) ans+=query(l,r,left,mid,fat<<1);

   if(r>mid) ans+=query(l,r,mid+1,right,fat<<1|1);

   return ans;

}

int main(){

   cin>>n>>m;

   for(int i=1;i<=n;i++) cin>>a[i];

   buildTree(1,1,n);//从1下标开始，在1～n范围构建线段树

   while(m--){

       cin>>c>>l>>r;

       if(c==2){

           cout<<query(l,r,1,n,1)<<endl;

       }

   }

   for(int i=1;i<=2*n;i++)cout<<t[i]<<" ";

   return 0;

}