封装好的模版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class tree {
 private:
  int v[10010], v1[10010];

 public:
  int n;
  int lowbit(int x) { return x & -x; }
  void sing_add(int x, int y) {
    for (; x <= n; x += lowbit(x)) v[x] += y;
  }
  int getsum(int *v, int x) {
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += v[x];
    return ans;
  }
  void mult_add(int l, int r, int v) {
    sing_add(l, v), sing_add(r + 1, -v);  // 将区间加差分为两个前缀加
  }

  long long getsum1(int l, int r) {
    return (r + 1ll) * getsum(v, r) - 1ll * l * getsum(v, l - 1) -
           (getsum(v1, r) - getsum(v1, l - 1));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

const int N = 1000005;
class segtree {
 private:
  int sum[N * 80], maxn[N * 80], minn[N * 80];
  int ls[N * 80], rs[N * 80];
  int seg;

 public:
  void init() {
    maxn[0] = -0x7fffffff;
    sum[0] = 0;
    minn[0] = 0x7fffffff;
  }
  void newpo(int &x) {
    x = ++seg;
    ls[x] = rs[x] = 0;
    sum[x] = 0;
    maxn[x] = -0x7fffffff;
    minn[x] = 0x7fffffff;
  }
  void pushup(int x) {
    sum[x] = sum[ls[x]] + sum[rs[x]];
    maxn[x] = max(maxn[ls[x]], maxn[rs[x]]);
    minn[x] = min(minn[ls[x]], minn[rs[x]]);
  }
  void ins(int &x, int l, int r, int pos, int val) {
    if (!x) newpo(x);
    if (l == r) {
      sum[x] += val;
      maxn[x] = pos;
      minn[x] = pos;
      return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
      ins(ls[x], l, mid, pos, val);
    else
      ins(rs[x], mid + 1, r, pos, val);
    pushup(x);
    return;
  }
  int querysum(int x, int l, int r, int ql, int qr) {
    //统计区间内一共有多少数
    if (!x) return 0;
    if (ql <= l && r <= qr) return sum[x];
    int mid = l + r >> 1, ret = 0;
    if (ql <= mid) ret += querysum(ls[x], l, mid, ql, qr);
    if (qr > mid) ret += querysum(rs[x], mid + 1, r, ql, qr);
    return ret;
  }
  int querymax(int x, int l, int r, int ql, int qr) {
    //统计区间内存在的数的最大值
    if (!x) return -0x7fffffff;
    if (ql <= l && r <= qr) return maxn[x];
    int mid = l + r >> 1, ret = -0x7fffffff;
    if (ql <= mid) ret = max(ret, querymax(ls[x], l, mid, ql, qr));
    if (qr > mid) ret = max(ret, querymax(rs[x], mid + 1, r, ql, qr));
    return ret;
  }
  int querymin(int x, int l, int r, int ql, int qr) {
    //统计区间内存在的数的最小值
    if (!x) return 0x7fffffff;
    if (ql <= l && r <= qr) return minn[x];
    int mid = l + r >> 1, ret = 0x7fffffff;
    if (ql <= mid) ret = min(ret, querymin(ls[x], l, mid, ql, qr));
    if (qr > mid) ret = min(ret, querymin(rs[x], mid + 1, r, ql, qr));
    return ret;
  }
};
/*
int n, a[N], rt = 0;
xds.init();
xds.ins(rt, 1, n, a[i], 1);
xds.querysum(1, 1, n, 1, n);
xds.querymax(1, 1, n, 1, n);
xds.querymin(1, 1, n, 1, n));
*/