int a[MAXN], ans[MAXN << ], lazy[MAXN << ];

 void PushUp(int rt) {

     ans[rt] = ans[rt << ] + ans[rt <<  | ];

 }

 void PushDown(int rt, int ln, int rn) { //ln表示左子树元素结点个数，rn表示右子树结点个数

     if (lazy[rt]) {

         lazy[rt << ] += lazy[rt];

         lazy[rt <<  | ] += lazy[rt];

         ans[rt << ] += lazy[rt] * ln;

         ans[rt <<  | ] += lazy[rt] * rn;

         lazy[rt] = ;

     }

 }

 //建树Build(1,n,1)

 void Build(int l, int r, int rt) {

     if (l == r) {

         ans[rt] = a[l];

         return;

     }

     int mid = (l + r) >> ;

     Build(l, mid, rt << );

     Build(mid + , r, rt <<  | );

     PushUp(rt);

 }

 //点更新Add(L,C,1,n,1)

 void Add(int L, int C, int l, int r, int rt) {

     if (l == r) {

         ans[rt] += C;

         return;

     }

     int mid = (l + r) >> ;

     //PushDown(rt,mid-l+1,r-mid); 若既有点更新又有区间更新，需要这句话

     if (L <= mid)

         Add(L, C, l, mid, rt << );

     else

         Add(L, C, mid + , r, rt <<  | );

     PushUp(rt);

 }

 //区间更新Upadate(L,R,C,1,n,1)

 void Update(int L, int R, int C, int l, int r, int rt) {

     if (L <= l && r <= R) {

         ans[rt] += C * (r - l + );

         lazy[rt] += C;

         return;

     }

     int mid = (l + r) >> ;

     PushDown(rt, mid - l + , r - mid);

     if (L <= mid)

         Update(L, R, C, l, mid, rt << );

     if (R > mid)

         Update(L, R, C, mid + , r, rt <<  | );

     PushUp(rt);

 }

 //区间查询Query(L,R,1,n,1)

 LL Query_sum(int L, int R, int l, int r, int rt) {

     if (L <= l && r <= R)

         return ans[rt];

     int mid = (l + r) >> ;

     PushDown(rt, mid - l + , r - mid); //若更新只有点更新，不需要这句

     LL ANS = ;

     if (L <= mid)

         ANS += Query_sum(L, R, l, mid, rt << );

     if (R > mid)

         ANS += Query_sum(L, R, mid + , r, rt <<  | );

     return ANS;

 }

 //区间最大值

 int Query_max(int L, int R, int l, int r, int rt) {

     if (L <= l&&R <= r)

         return ans[rt];

     int mid = (l + r) >> ;

     PushDown(rt, mid - l + , r - mid);

     int ANS = ;

     if (L <= mid) ANS = max(ANS, Query_max(L, R, l, mid, rt << ));

     if (R > mid) ANS = max(ANS, Query_max(L, R, mid + , r, rt <<  | ));

     return ANS;

 }

 //单点查询

 int Query(int L, int R, int l, int r, int rt) {

     if (L == l&&R == r)

         return ans[rt];

     int mid = (l + r) >> ;

     PushDown(rt, mid - l + , r - mid);

     int ANS = ;

     if (L <= mid)

         ANS = Query(L, R, l, mid, rt << );

     if (R > mid)

         ANS = Query(L, R, mid + , r, rt <<  | );

     return ANS;

 }