[关闭]
@Dmaxiya 2022-11-12T09:55:17.000000Z 字数 5361 阅读 1179

RMQ 问题

板子

树状数组

一维树状数组

  1. int n;
  2. int sum[maxn];
  3. // 树状数组下标范围为[1, n]，查询[1, i] 区间和
  4. int lowbit(int x) {
  5.     return x & (-x);
  6. }
  8. void update(int i, int x) {
  9.     while(i <= n) {
  10.         sum[i] += x;
  11.         i += lowbit(i);
  12.     }
  13. }
  15. int query(int i) {
  16.     int ret = 0;
  17.     while(i > 0) {
  18.         ret += sum[i];
  19.         i -= lowbit(i);
  20.     }
  21.     return ret;
  22. }

二维树状数组

  1. int n, m;
  2. int sum[maxn][maxm];
  3. // 树状数组下标范围为[(1, 1), (n, m)]，查询[(1, 1), (i, j)] 区间和
  4. int lowbit(int x) {
  5.     return x & (-x);
  6. }
  8. void update(int i, int j, int x) {
  9.     while(i <= n) {
  10.         int jj = j;
  11.         while(jj <= m) {
  12.             sum[i][jj] += x;
  13.             jj += lowbit(jj);
  14.         }
  15.         i += lowbit(i);
  16.     }
  17. }
  19. int query(int i, int j) {
  20.     int ret = 0;
  21.     while(i > 0) {
  22.         int jj = j;
  23.         while(jj > 0) {
  24.             ret += sum[i][jj];
  25.             jj -= lowbit(jj);
  26.         }
  27.         i -= lowbit(i);
  28.     }
  29.     return ret;
  30. }

ST 表

  1. const int maxn = 100000 + 100;
  2. const int Log = 40;
  3. int stmax[maxn][Log], stmin[maxn][Log], mn[maxn];
  4. int num[maxn];
  5. // 下标范围为[1,n]，每次查询区间为[L, R]
  6. void Init() {
  7.     mn[0] = -1;
  8.     for(int i = 1; i <= n; ++i) {
  9.         mn[i] = ((i & (i - 1)) == 0)? mn[i - 1] + 1: mn[i - 1];
  10.         stmax[i][0] = stmin[i][0] = num[i];
  11.     }
  12.     for(int j = 1; j <= mn[n]; ++j) {
  13.         for(int i = 1; i + (1 << j) - 1 <= n; ++i) {
  14.             stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
  15.             stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
  16.         }
  17.     }
  18. }
  20. int rmq_max(int L, int R) {
  21.     int k = mn[R - L + 1];
  22.     return max(stmax[L][k], stmax[R - (1 << k) + 1][k]);
  23. }
  25. int rmq_min(int L, int R) {
  26.     int k = mn[R - L + 1];
  27.     return min(stmin[L][k], stmin[R - (1 << k) + 1][k]);
  28. }

线段树

单点替换、增减、区间求和、最值（HDU 1166 / POJ 3264）

  1. const int maxn = 50000 + 100;
  3. struct SegmentTree {
  4.     int sum[maxn << 2], mx[maxn << 2], mn[maxn << 2];
  6.     inline int lson(int rt) {
  7.         return rt << 1;
  8.     }
  10.     inline int rson(int rt) {
  11.         return rt << 1 | 1;
  12.     }
  14.     void pushUp(int rt) {
  15.         int l = lson(rt);
  16.         int r = rson(rt);
  17.         sum[rt] = sum[l] + sum[r];
  18.         mx[rt] = max(mx[l], mx[r]);
  19.         mn[rt] = min(mn[l], mn[r]);
  20.     }
  22.     void build(int rt, int l, int r) {
  23.         if(l == r) {
  24.             scanf("%d", &sum[rt]);
  25.             mn[rt] = mx[rt] = sum[rt];
  26.             return ;
  27.         }
  28.         int m = (l + r) >> 1;
  29.         build(lson(rt), l, m);
  30.         build(rson(rt), m + 1, r);
  31.         pushUp(rt);
  32.     }
  34.     void update(int rt, int l, int r, int idx, int x) {
  35.         if(l == r) {
  36.             sum[rt] = mx[rt] = mn[rt] = x;
  37.             return ;
  38.         }
  39.         int m = (l + r) >> 1;
  40.         if(idx <= m) {
  41.             update(lson(rt), l, m, idx, x);
  42.         } else {
  43.             update(rson(rt), m + 1, r, idx, x);
  44.         }
  45.         pushUp(rt);
  46.     }
  48.     void add(int rt, int l, int r, int idx, int x) {
  49.         if(l == r) {
  50.             sum[rt] += x;
  51.             mx[rt] = mn[rt] = sum[rt];
  52.             return ;
  53.         }
  54.         int m = (l + r) >> 1;
  55.         if(idx <= m) {
  56.             add(lson(rt), l, m, idx, x);
  57.         } else {
  58.             add(rson(rt), m + 1, r, idx, x);
  59.         }
  60.         pushUp(rt);
  61.     }
  63.     int queryMax(int rt, int l, int r, int L, int R) {
  64.         if(L <= l && r <= R) {
  65.             return mx[rt];
  66.         }
  67.         int m = (l + r) >> 1;
  68.         int ret = INT_MIN;
  69.         if(L <= m) {
  70.             ret = max(ret, queryMax(lson(rt), l, m, L, R));
  71.         }
  72.         if(m < R) {
  73.             ret = max(ret, queryMax(rson(rt), m + 1, r, L, R));
  74.         }
  75.         return ret;
  76.     }
  78.     int queryMin(int rt, int l, int r, int L, int R) {
  79.         if(L <= l && r <= R) {
  80.             return mn[rt];
  81.         }
  82.         int m = (l + r) >> 1;
  83.         int ret = INT_MAX;
  84.         if(L <= m) {
  85.             ret = min(ret, queryMin(lson(rt), l, m, L, R));
  86.         }
  87.         if(m < R) {
  88.             ret = min(ret, queryMin(rson(rt), m + 1, r, L, R));
  89.         }
  90.         return ret;
  91.     }
  93.     int querySum(int rt, int l, int r, int L, int R) {
  94.         if(L <= l && r <= R) {
  95.             return sum[rt];
  96.         }
  97.         int m = (l + r) >> 1;
  98.         int ret = 0;
  99.         if(L <= m) {
  100.             ret += querySum(lson(rt), l, m, L, R);
  101.         }
  102.         if(R > m) {
  103.             ret += querySum(rson(rt), m + 1, r, L, R);
  104.         }
  105.         return ret;
  106.     }
  107. };

区间增减，区间求和（HDU 1556）

  1. const int maxn = 100000 + 100;
  3. struct SegmentTree {
  4.     int sum[maxn << 2], lazy[maxn << 2];
  6.     inline int lson(int rt) {
  7.         return rt << 1;
  8.     }
  10.     inline int rson(int rt) {
  11.         return rt << 1 | 1;
  12.     }
  14.     void pushUp(int rt) {
  15.         sum[rt] = sum[lson(rt)] + sum[rson(rt)];
  16.     }
  18.     void pushDown(int rt, int len) {
  19.         if (lazy[rt] == 0) {
  20.             return ;
  21.         }
  22.         int l = lson(rt);
  23.         int r = rson(rt);
  24.         lazy[l] += lazy[rt];
  25.         lazy[r] += lazy[rt];
  26.         sum[l] += (len - (len >> 1)) * lazy[rt];
  27.         sum[r] += (len >> 1) * lazy[rt];
  28.         lazy[rt] = 0;
  29.     }
  31.     void build(int rt, int l, int r) {
  32.         lazy[rt] = 0;
  33.         if(l == r) {
  34.             scanf("%d", &sum[rt]);
  35.             return ;
  36.         }
  37.         int m = (l + r) >> 1;
  38.         build(lson(rt), l, m);
  39.         build(rson(rt), m + 1, r);
  40.         pushUp(rt);
  41.     }
  43.     void add(int rt, int l, int r, int L, int R, int x) {
  44.         if(L <= l && r <= R) {
  45.             lazy[rt] += x;
  46.             sum[rt] += (r - l + 1) * x;
  47.             return ;
  48.         }
  49.         pushDown(rt, r - l + 1);
  50.         int m = (l + r) >> 1;
  51.         if(L <= m) {
  52.             add(lson(rt), l, m, L, R, x);
  53.         }
  54.         if(m < R) {
  55.             add(rson(rt), m + 1, r, L, R, x);
  56.         }
  57.         pushUp(rt);
  58.     }
  60.     int query(int rt, int l, int r, int L, int R) {
  61.         if(L <= l && r <= R) {
  62.             return sum[rt];
  63.         }
  64.         pushDown(rt, r - l + 1);
  65.         int m = (l + r) >> 1;
  66.         int ret = 0;
  67.         if(L <= m) {
  68.             ret += query(lson(rt), l, m, L, R);
  69.         }
  70.         if(R > m) {
  71.             ret += query(rson(rt), m + 1, r, L, R);
  72.         }
  73.         return ret;
  74.     }
  75. };

主席树（POJ 2104）

  1. const int Log = 20;
  2. const int maxn = 200000;
  3. const int t_maxn = maxn * Log;
  4. int n, cnt;
  5. int root[maxn], Sum[t_maxn], lson[t_maxn], rson[t_maxn];
  6. // cnt 每次需要清空为 0
  7. // maxn 为主席树节点个数
  8. // 线段树下标从 1 开始
  9. // root[i] 为第 i 棵线段树的根节点
  10. // Sum 为线段树，lson 和 rson 是节点 i 的左右子节点
  11. void Build(int &x, int l, int r) {
  12.     x = cnt++;
  13.     Sum[x] = 0;
  14.     if(l == r) {
  15.         return ;
  16.     }
  17.     int m = (l + r) >> 1;
  18.     Build(lson[x], l, m);
  19.     Build(rson[x], m + 1, r);
  20. }
  22. void update(int &x, int last, int l, int r, int pos) {
  23.     x = cnt++;
  24.     lson[x] = lson[last];
  25.     rson[x] = rson[last];
  26.     if(l == r) {
  27.         Sum[x] = Sum[last] + 1;
  28.         return ;
  29.     }
  30.     int m = (l + r) >> 1;
  31.     if(pos <= m) {
  32.         update(lson[x], lson[last], l, m, pos);
  33.     } else {
  34.         update(rson[x], rson[last], m + 1, r, pos);
  35.     }
  36.     Sum[x] = Sum[lson[x]] + Sum[rson[x]];
  37. }
  39. int query(int L, int R, int l, int r, int k) {
  40.     if(l == r) {
  41.         return l;
  42.     }
  43.     int m = (l + r) >> 1;
  44.     int tmp = Sum[lson[R]] - Sum[lson[L]];
  45.     if(k <= tmp) {
  46.         return query(lson[L], lson[R], l, m, k);
  47.     } else {
  48.         return query(rson[L], rson[R], m + 1, r, k - tmp);
  49.     }
  50. }

笛卡尔树（HDU 6305）

  1. const int maxn = 1000000 + 100;
  2. // 数组下标从 1 开始
  3. struct Tree {
  4.     int root, top, n;
  5.     int sta[maxn], l[maxn], r[maxn];
  6.     bool vis[maxn];
  8.     void build(int *num, int nn) {
  9.         n = nn;
  10.         top = 0;
  11.         memset(l, 0, sizeof(int) * (n + 1));
  12.         memset(r, 0, sizeof(int) * (n + 1));
  13.         memset(vis, 0, sizeof(bool) * (n + 1));
  14.         for(int i = 1; i <= n; ++i) {
  15.             int tmp = top;
  16.             while(top > 0 && num[sta[top - 1]] < num[i]) {
  17.                 --top;
  18.             }
  19.             if(top != 0) {
  20.                 r[sta[top - 1]] = i;
  21.             }
  22.             if(top < tmp) {
  23.                 l[i] = sta[top];
  24.             }
  25.             sta[top++] = i;
  26.         }
  27.         for(int i = 1; i <= n; ++i) {
  28.             vis[l[i]] = vis[r[i]] = true;
  29.         }
  30.         for(int i = 1; i <= n; ++i) {
  31.             if(!vis[i]) {
  32.                 root = i;
  33.             }
  34.         }
  35.     }
  36. };

莫队

  1. const int maxn = 100000 + 100;
  2. // 下标范围为 [1, n]
  3. struct Node {
  4.     int l, r;
  5.     int id;
  6.     static int pos[maxn];
  8.     void init() {
  9.         int sz = sqrt(maxn);
  10.         for (int i = 0; i < maxn; ++i) {
  11.             pos[i] = i / sz;
  12.         }
  13.     }
  14. };
  16. int Node::pos[maxn] = {};
  18. bool operator<(const Node &a, const Node &b) {
  19.     if(Node::pos[a.l] == Node::pos[b.l]) {
  20.         return a.r < b.r;
  21.     }
  22.     return Node::pos[a.l] < Node::pos[b.l];
  23. }
  25. int n, q, l, r, sz;
  26. int ans[maxn];
  27. Node node[maxn];
  29. void add(int x);
  30. void del(int x);
  31. int getAns();
  33. void mo() {
  34.     l = 1;
  35.     r = 0;
  36.     sort(node, node + q);
  37.     for (int i = 0; i < q; ++i) {
  38.         while (r < node[i].r) {
  39.             ++r;
  40.             add(r);
  41.         }
  42.         while (l > node[i].l) {
  43.             --l;
  44.             add(l);
  45.         }
  46.         while (r > node[i].r) {
  47.             del(r);
  48.             --r;
  49.         }
  50.         while (l < node[i].l) {
  51.             del(l);
  52.             ++l;
  53.         }
  54.         ans[node[i].id] = getAns();
  55.     }
  56. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注