过于复杂的线段树

以下是一个过于臃肿的线段树模板。。。。。

代码不要写太长。。。。。。

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int MAX[maxn<<2];
int MIN[maxn<<2];
int SUM[maxn<<2];
long long lazy[maxn<<2];
int max(int a,int b){if(a>b)return a;else return b;}
int min(int a,int b){if(a<b)return a;else return b;}
void PushUP(int rt)
{
  MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
  MIN[rt] = min(MIN[rt<<1] , MIN[rt<<1|1]);
  SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}
void build(int l,int r,int rt) {
  if (l == r)
    {
    scanf("%d",&MAX[rt]);
    MIN[rt] = MAX[rt];
    SUM[rt] = MAX[rt];
    //printf("mi = %d\n",MIN[rt]);
  //	printf("ma = %d\n",MAX[rt]);
    return ;
  }
  int m = (l + r) >> 1;
  build(lson);
  build(rson);
  PushUP(rt);
}
void update(int p,int tihuan,int l,int r,int rt)
{
  if (l == r) {
    MAX[rt] = tihuan;
    MIN[rt] = tihuan;
    SUM[rt] = tihuan;
    return ;
  }
  int m = (l + r) >> 1;
  if (p <= m) update(p , tihuan ,lson);
  else update(p , tihuan , rson);
  PushUP(rt);
}
void putup(int rt)
{
  SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}
void putdown(int rt,int m)
{
  if (lazy[rt])
  {
    lazy[rt<<1] += lazy[rt];
    lazy[rt<<1|1] += lazy[rt];
    SUM[rt<<1] += lazy[rt] * (m - (m >> 1));
    SUM[rt<<1|1] += lazy[rt] * (m >> 1);
    lazy[rt] = 0;
  }
}
void update(int L,int R,int c,int l,int r,int rt)
{
  if (L <= l && r <= R)
  {
    lazy[rt] += c;
    SUM[rt] += (long long)c * (r - l + 1);
    return ;
  }
  putdown(rt , r - l + 1);
  int m = (l + r) >> 1;
  if (L <= m) update(L , R , c , lson);
  if (m < R) update(L , R , c , rson);
  putup(rt);
}

void update1(int p,int add,int l,int r,int rt)
{
  if (l == r) {
    SUM[rt] = SUM[rt] + add;
    return ;
  }
  putdown(rt , r - l + 1);
  int m = (l + r) >> 1;
  if (p <= m) update1(p , add ,lson);
  else update1(p , add , rson);
  PushUP(rt);
}
int query(int L,int R,int l,int r,int rt)
{
  if (L <= l && r <= R)
  {
    return MAX[rt];
  }
  putdown(rt , r - l + 1);
  int m = (l + r) >> 1;
  int ret = -1;
  if (L <= m) ret = max(ret , query(L , R , lson));
  if (R > m)  ret =  max(ret , query(L , R , rson));
  return ret;
}
int query1(int L,int R,int l,int r,int rt)
{
  if (L <= l && r <= R)
  {
    return MIN[rt];
  }
  putdown(rt , r - l + 1);
  int m = (l + r) >> 1;
  int ret = 99999;
  if (L <= m) ret = min(ret , query1(L , R , lson));
  if (R > m)  ret =  min(ret , query1(L , R , rson));
  return ret;
}
int queryhe(int L,int R,int l,int r,int rt)
{
  if (L <= l && r <= R)
  {
    return SUM[rt];
  }
  putdown(rt , r - l + 1);
  int m = (l + r) >> 1;
  int ret = 0;
  if (L <= m) ret += queryhe(L , R , lson);
  if (R > m)  ret +=  queryhe(L , R , rson);
  return ret;
}
int main()
{
  int n , m;
  scanf("%d",&n);
    build(1 , n , 1);
    scanf("%d",&m);
    while (m --) {
      char op[2];
      int a , b , c;
      scanf("%s%d",op,&a);
      if(op[0]=='2')
      {
        printf("%d\n",queryhe(a , a , 1 , n , 1));
      }
      else if(op[0]=='1')
      {
        scanf("%d%d",&b,&c);
        update(a , b , c , 1 , n , 1);
      }
    }
  return 0;
}

 

此条目发表在CODEVS, 线段树分类目录。将固定链接加入收藏夹。