（单点修改，区间求最值）

    1. struct SegTree {
    2.     struct node {
    3.         int l, r, mi;
    4.     }tr[N<<2];
    5.     void pushup(int u) {
    6.         tr[u].mi = min(tr[u<<1].mi, tr[u<<1|1].mi);
    7.     }
    8.     void build(int u, int l, int r) {
    9.         tr[u].l = l, tr[u].r = r;
    10.         tr[u].mi = INF;
    11.         if (l == r) {
    12.             tr[u].mi = a[r];
    13.             return ;
    14.         }
    15.         int mid = l+r>>1;
    16.         build(u<<1, l, mid);
    17.         build(u<<1|1, mid+1, r);
    18.         pushup(u);
    19.     }
    20.     void update(int u, int p, int k) {
    21.         if (tr[u].l == tr[u].r) {
    22.             tr[u].mi = k;
    23.       a[p] = k;
    24.             return ;
    25.         }
    26.         int mid = tr[u].l+tr[u].r>>1;
    27.         if (p <= mid) {
    28.             update(u<<1, p, k);    
    29.         } else {
    30.             update(u<<1|1, p, k);
    31.         }
    32.         pushup(u);
    33.     }
    34.     int query(int u, int L, int R) {
    35.         if (tr[u].l>=L && tr[u].r<=R) {
    36.             return tr[u].mi;
    37.         }
    38.         int mid = tr[u].l+tr[u].r>>1;
    39.         int res = INF; 
    40.         if (mid >= L) 
    41.             res = min(res, query(u<<1, L, R));
    42.         if (mid < R)
    43.             res = min(res, query(u<<1|1, L, R));
    44.         return res;
    45.     } 
    46. }tree;

    （区间修改，区间求最值）

    1. struct SegmentTree {
    2.     struct node {
    3.         int l, r;
    4.         int mx, tag;
    5.     }tr[N<<2];
    6.     void pushup(int u) {
    7.         tr[u].mx = max(tr[u<<1].mx, tr[u<<1|1].mx);
    8.     }
    9.     void eval(int u, int tag) {
    10.         tr[u].tag += tag;
    11.         tr[u].mx += tag;
    12.     }
    13.     void pushdown(int u) {
    14.         eval(u<<1, tr[u].tag);
    15.         eval(u<<1|1, tr[u].tag);
    16.         tr[u].tag = 0;
    17.     }
    18.     void build(int u, int l, int r) {
    19.         tr[u].l = l, tr[u].r = r;
    20.         tr[u].tag = 0, tr[u].mx = -0x3f3f3f3f;
    21.         if (l == r) {
    22.             tr[u].mx = w[l];
    23.             return ;
    24.         }
    25.         int mid = l+r>>1;
    26.         build(u<<1, l, mid);
    27.         build(u<<1|1, mid+1, r);
    28.         pushup(u);
    29.     }
    30.     void update(int u, int l, int r, int k) {
    31.         if (l<=tr[u].l && r>=tr[u].r) {
    32.             eval(u, k);
    33.             return;
    34.         }
    35.         pushdown(u);
    36.         int mid = tr[u].l+tr[u].r>>1;
    37.         if (l <= mid) 
    38.             update(u<<1, l, r, k);
    39.         if (r > mid) 
    40.             update(u<<1|1, l, r, k);
    41.         pushup(u);
    42.     }
    43.     int query(int u, int l, int r) {
    44.         if (l <= tr[u].l && r >= tr[u].r) 
    45.             return tr[u].mx;
    46.         pushdown(u);
    47.         int mid = tr[u].l+tr[u].r>>1;
    48.         int res = 0;
    49.         if (l <= mid) 
    50.             res = max(res, query(u<<1, l, r));
    51.         if (r > mid) 
    52.             res = max(res, query(u<<1|1, l, r));
    53.         pushup(u);
    54.         return res;
    55.     }
    56. }tree;

    （区间+k，区间求和）

    1. struct SegTr{
    2.     struct node {
    3.         int l, r;
    4.         int sum, tag;
    5.     }tr[N<<2];
    6.     void pushup(int u) {
    7.         tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
    8.     }
    9.     void eval(int u, int tag) {
    10.         tr[u].sum += (tr[u].r-tr[u].l+1)*tag;
    11.         tr[u].tag += tag;
    12.     }
    13.     void pushdown(int u) {
    14.         if (tr[u].tag) {
    15.             eval(u<<1, tr[u].tag);
    16.             eval(u<<1|1, tr[u].tag);
    17.             tr[u].tag = 0;
    18.         }
    19.     }
    20.     void build(int u, int l, int r) {
    21.         tr[u].l = l, tr[u].r = r;
    22.         tr[u].tag = 0;
    23.         if (l == r) {
    24.             tr[u].sum = b[r];
    25.             return ;
    26.         }
    27.         int mid = l+r>>1;
    28.         build(u<<1, l, mid);
    29.         build(u<<1|1, mid+1, r);
    30.         pushup(u);
    31.     }
    32.     void update(int u, int l, int r, int k) {
    33.         if (tr[u].l>=l && tr[u].r<=r) {
    34.             eval(u, k);
    35.             return ;
    36.         }
    37.         pushdown(u);
    38.         int mid = tr[u].l+tr[u].r>>1;
    39.         if (l <= mid) 
    40.             update(u<<1, l, r, k);
    41.         if (r > mid)
    42.             update(u<<1|1, l, r, k);
    43.         pushup(u);
    44.     }
    45.     int query(int u, int l, int r) {
    46.         if (tr[u].l>=l && tr[u].r<=r) 
    47.             return tr[u].sum;
    48.         pushdown(u);
    49.         int mid = tr[u].l+tr[u].r>>1;
    50.         int res = 0;
    51.         if (l <= mid) 
    52.             res += query(u<<1, l, r);
    53.         if (r > mid)
    54.             res += query(u<<1|1, l, r); 
    55.         return res;
    56.     }
    57. }tree;

    （单点修改，区间求最长连续01序列）

    1. struct SegTree {
    2.     struct node {
    3.         int l, r, len;
    4.         int lv, rv;
    5.         int lmx, rmx, mx;
    6.     }tr[N<<2];
    7.     void pushup(int u) {
    8.         tr[u].lmx = tr[u<<1].lmx;
    9.         tr[u].rmx = tr[u<<1|1].rmx;
    10.         tr[u].lv = tr[u<<1].lv;
    11.         tr[u].rv = tr[u<<1|1].rv;
    12.         tr[u].mx = max(tr[u<<1].mx, tr[u<<1|1].mx);
    13.         if (tr[u<<1].rv != tr[u<<1|1].lv) {
    14.             tr[u].mx = max(tr[u].mx, tr[u<<1].rmx+tr[u<<1|1].lmx);
    15.             if (tr[u<<1].mx == tr[u<<1].len) {
    16.                 tr[u].lmx = tr[u<<1|1].lmx+tr[u<<1].len;
    17.             }
    18.             if (tr[u<<1|1].mx == tr[u<<1|1].len) {
    19.                 tr[u].rmx = tr[u<<1].rmx+tr[u<<1|1].len; 
    20.             }
    21.         } 
    22.     }
    23.     void build(int u, int l,  int r) {
    24.         tr[u].l = l, tr[u].r = r;
    25.         tr[u].len = r-l+1;
    26.         if (l == r) {
    27.             tr[u].lv = tr[u].rv = 1;
    28.             tr[u].lmx = tr[u].rmx = 1;
    29.             tr[u].mx = 1;
    30.             return ;
    31.         }
    32.         int mid = l+r>>1;
    33.         build(u<<1, l, mid);
    34.         build(u<<1|1, mid+1, r);
    35.         pushup(u);  
    36.     }
    37.     void update(int u, int pos) {
    38.         if (tr[u].l == tr[u].r) {
    39.             tr[u].lv ^= 1;
    40.             tr[u].rv = tr[u].lv;
    41.             return ;
    42.         }
    43.         int mid = tr[u].l+tr[u].r>>1;
    44.         if (pos <= mid)
    45.             update(u<<1, pos);
    46.         if (pos > mid)
    47.             update(u<<1|1, pos); 
    48.         pushup(u);
    49.     }
    50.     int query() {
    51.         return max(tr[1].mx, max(tr[1].lmx, tr[1].rmx));
    52.     }
    53. }tree;

    （区间修改，区间求最长连续0序列）

    struct SegTree {
    struct node {
        int l, r, len;
        int lmx, rmx, sum;
        int tag;
    }tr[N<<2];

    void pushup(int u) {
        if (tr[u<<1].sum == tr[u<<1].len) {
            tr[u].lmx = tr[u<<1].len+tr[u<<1|1].lmx;
        } else {
            tr[u].lmx = tr[u<<1].lmx;
        }
        if (tr[u<<1|1].sum == tr[u<<1|1].len) {
            tr[u].rmx = tr[u<<1].rmx+tr[u<<1|1].len;
        } else {
            tr[u].rmx = tr[u<<1|1].rmx;
        }
        tr[u].sum = max(tr[u<<1].rmx+tr[u<<1|1].lmx, max(tr[u<<1].sum, tr[u<<1|1].sum));
    }

    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r;
        tr[u].tag = 0;
        tr[u].sum = tr[u].len = tr[u].lmx = tr[u].rmx = r-l+1;
        if (l == r) {
            return ;
        } 
        int mid = l+r>>1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        pushup(u);
    }

    void eval(int u, int tag) {
        if (tag == 1) {
            tr[u].tag = 1;
            tr[u].sum = tr[u].lmx = tr[u].rmx = 0;
        } else if (tag == 2) {
            tr[u].tag = 2;
            tr[u].sum = tr[u].lmx = tr[u].rmx = tr[u].len;
        }
    } 

    void pushdown(int u) {
        if (tr[u].tag == 0) {
            return ;
        } else if (tr[u].tag == 1) {
            eval(u<<1, 1);
            eval(u<<1|1, 1);
        } else if (tr[u].tag == 2) {
            eval(u<<1, 2);
            eval(u<<1|1, 2);
        }
        tr[u].tag = 0;
    } 

    void update(int u, int l, int r, int tag) {
        if (tr[u].l>=l && tr[u].r<=r) {
            eval(u, tag);
            return ;
        }
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        if (l <= mid)
            update(u<<1, l, r, tag);
        if (r > mid)
            update(u<<1|1, l, r, tag);
        pushup(u); 
    }

    int query(int u, int l, int r, int len) {
        if (l == r)
            return l;
        pushdown(u);
        int mid = l+r>>1;
        if (tr[u<<1].sum >= len) 
            return query(u<<1, l, mid, len);
        if (tr[u<<1].rmx+tr[u<<1|1].lmx >= len) {
            return mid-tr[u<<1].rmx+1; 
        } else {
            return query(u<<1|1, mid+1, r, len);
        }
    }
}tree;

    拆位线段树（区间异或x，区间求和）

    struct SegTree {
    struct node {
        int l, r;
        int tag, sum;
    }tr[21][N*4];
    void pushup(int id, int u) {
        tr[id][u].sum = tr[id][u<<1].sum+tr[id][u<<1|1].sum;
    }
    void build(int id, int u, int l, int r) {
        tr[id][u].l = l, tr[id][u].r = r;
        if (l == r) {
            tr[id][u].sum = (a[l]&(1<<id))!=0;
            return ;
        }
        int mid = l + r >> 1;
        build(id, u<<1, l, mid);
        build(id, u<<1|1, mid+1, r); 
        pushup(id, u);
    }
    void eval(int id, int u) {
        int len = tr[id][u].r - tr[id][u].l + 1; 
        tr[id][u].sum = len - tr[id][u].sum;
        tr[id][u].tag ^= 1;
    }
    void pushdown(int id, int u) {
        if (tr[id][u].tag != 0) {
            eval(id, u<<1);
            eval(id, u<<1|1);
            tr[id][u].tag = 0;
        }
    }
    void update(int id, int u, int l, int r) {
        if (tr[id][u].l >= l && tr[id][u].r <= r) {
            eval(id, u);
            return ;
        }
        pushdown(id, u);
        int mid = tr[id][u].l + tr[id][u].r >> 1;
        if (l <= mid) 
            update(id, u<<1, l, r);
        if (r > mid)
            update(id, u<<1|1, l, r);
        pushup(id, u);
    }
    int query(int id, int u, int l, int r) {
        if (tr[id][u].l >= l && tr[id][u].r <= r)
            return tr[id][u].sum;
        pushdown(id, u);
        int res = 0;
        int mid = tr[id][u].l + tr[id][u].r >> 1;
        if (l <= mid)
            res += query(id, u<<1, l, r);
        if (r > mid)
            res += query(id, u<<1|1, l, r);
        return res; 
    }
}tree;