终于大吉了

今天学了线段树，觉得有一点难，还没完全理解模板，只会打简单的模板题

线段树模板

0.wwq打的模板

void pushup(int p) {
    tree[p] = tree[p << 1] + tree[p1 << | 1];
}
void pushdown(int p, int l, int r) {
    int d = tag[p];
    int mid = (l + r) >> 1;
    tree[p << 1] += d*(mid - l + 1);
    tree[p << 1 | 1] += d*(r - mid);
    tag[p << 1] += d;
    tag[p << 1 | 1] += d;
    tag[p] = 0;
}
void undate(int l, int r, int pl, int pr, int p, int d) {
    if (pl >= l && pr <= r) {
        tree[p] += d*(pr - pl + 1);
        tag[p] += d;
        return;
    }
    if (tag[p])pushdown(p, pl, pr);
    int mid = (pl + pr) >> 1;
    if (l <= mid)undate(l, r, d, p << 1, pl, mid);
    if (r >= mid + 1)undate(l, r, d, p << 1 | 1, mid + 1, pr);
    pushup(p);
}
int query(int l, int r, int pl, int pr, int p) {
    if (l <= pl && pr <= r) {
        return tree[p];
    }
    pushdown(p, pl, pr);
    int mid = (pl + pr) >> 1;
    int ret = 0;
    if (l <= mid)ret += query(l, r, p << 1, pl, mid);
    if (r >= mid + 1)ret += query(l, r, p << 1 | 1, mid + 1, pr);
    return ret;
}

1.建树

//建树
void build(int ql, int qr, int p) {
    if (ql == qr) {
        d[p] = a[ql];
        return;
    }
    int m = ql + ((qr - ql) >> 1);
    build(ql, m, p * 2), build(m + 1, qr, p * 2 + 1);
    d[p] = d[p * 2] + d[(p * 2) + 1];
}

2.区间修改（有懒标记）

//区间修改（有懒标记）
void update(int l, int r, int ql, int qr, int p, int c) {
    if (l  1);
    if (lazy[p] && ql != qr) {
        d[p * 2] += lazy[p] * (m - ql + 1), d[p * 2 + 1] += lazy[p] * (qr - m);
        lazy[p * 2] += lazy[p], lazy[p * 2 + 1] += lazy[p];
        lazy[p] = 0;
    }
    if (l  m) update(l, r, m + 1, qr, p * 2 + 1,c);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

3.区间查询（有懒标记）

//区间查询（有懒标记）
int getsum(int l, int r, int ql, int qr, int p) {
    if (l  1);
    if (lazy[p]) {
        d[p * 2] += lazy[p] * (m - ql + 1), d[p * 2 + 1] += lazy[p] * (qr - m);
        lazy[p * 2] += lazy[p], lazy[p * 2 + 1] += lazy[p];
        lazy[p] = 0;
    }
    int sum = 0;
    if (l  m) sum += getsum(l, r, m + 1, qr, p * 2 + 1);
    return sum;
}

other.3+4.如果你是要实现区间修改为某一个值而不是加上某一个值的话，代码如下：

//如果你是要实现区间修改为某一个值而不是加上某一个值的话，代码如下：
void update(int l, int r, int c, int ql, int qr, int p) {
    if (l  1);
    // 额外数组储存是否修改值
    if (v[p]) {
        d[p * 2] = lazy[p] * (m - ql + 1), d[p * 2 + 1] = lazy[p] * (qr - m);
        lazy[p * 2] = lazy[p * 2 + 1] = lazy[p];
        v[p * 2] = v[p * 2 + 1] = 1;
        v[p] = 0;
    }
    if (l  m) update(l, r, c, m + 1, qr, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

int getsum(int l, int r, int ql, int qr, int p) {
    if (l  1);
    if (v[p]) {
        d[p * 2] = lazy[p] * (m - ql + 1), d[p * 2 + 1] = lazy[p] * (qr - m);
        lazy[p * 2] = lazy[p * 2 + 1] = lazy[p];
        v[p * 2] = v[p * 2 + 1] = 1;
        v[p] = 0;
    }
    int sum = 0;
    if (l  m) sum += getsum(l, r, m + 1, qr, p * 2 + 1);
    return sum;
}

动态开点线段树

1.单点修改

//单点修改
// root 表示整棵线段树的根结点；cnt 表示当前结点个数
int n, cnt, root;
int sum[n * 2], ls[n * 2], rs[n * 2];

// 用法：update(root, 1, n, x, f); 其中 x 为待修改节点的编号
void update(int& p, int s, int t, int x, int f) {  // 引用传参
  if (!p) p = ++cnt;  // 当结点为空时，创建一个新的结点
  if (s == t) {
    sum[p] += f;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (x <= m)
    update(ls[p], s, m, x, f);
  else
    update(rs[p], m + 1, t, x, f);
  sum[p] = sum[ls[p]] + sum[rs[p]];  // pushup
}

2.区间询问

//区间询问
// 用法：query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r) {
  if (!p) return 0;  // 如果结点为空，返回 0
  if (s >= l && t > 1), ans = 0;
  if (l  m) ans += query(rs[p], m + 1, t, l, r);
  return ans;
}

我猜你模式背景下，委员会决定一下