线段树模板

开局宏定义：

#include<bits/stdc++.h>
#define int long long
#define lson (now << 1)//现结点的左孩子
#define rson (now << 1 | 1)//右孩子
using namespace std;

结构体定义：

struct Node{
    int l ,r;  //表示左右区间
    int max, sum; //其他数据域
}tree[N << 2] //=N*4，N指节点个数

常规操作

• 向上回溯：

void push_up(int now){
    tree[now].sum += tree[lson].sum + tree[rson].sum;
    tree[now].max = max(tree[lson].max, tree[rson].max);
}

• 建树：

void build(int now, int l, int r) {
    tree[now].left = l; tree[now].right = r;

    if(l == r){
        tree[now].sum = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(lson, l, mid),build(rson, mid+1, r);

    push_up(now);
}

• 单点更新:

void update(int now, int pos, int key){
    if(tree[now].left == l and tree[now].right <= r){
        tree[now].sum = tree[now].max = key;
        tree[now].lazy += key;
        return;        
    }

    int mid = (tree[now].left + tree[now].right) >> 1;

    if(l <= mid) update(lson, pos, key);
    if(r > mid) update(rson, pos, key);

    push_up(now);
}

• 查询区间和：

 int query(int now, int l, int r){
    if( l <= tree[now].left and tree[now].right <= r)
          return tree[now],sum;
    
    int mid = (tree[now].left + tree[now].rigth) >> 1;

    if(l <= mid) retur query(lson, l, r);
    if(r > mid) return query(rson, l, r);
}