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

RMQ 问题

板子


树状数组

一维树状数组

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

二维树状数组

  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. }
  7. void update(int i, int j, int x) {
  8. while(i <= n) {
  9. int jj = j;
  10. while(jj <= m) {
  11. sum[i][jj] += x;
  12. jj += lowbit(jj);
  13. }
  14. i += lowbit(i);
  15. }
  16. }
  17. int query(int i, int j) {
  18. int ret = 0;
  19. while(i > 0) {
  20. int jj = j;
  21. while(jj > 0) {
  22. ret += sum[i][jj];
  23. jj -= lowbit(jj);
  24. }
  25. i -= lowbit(i);
  26. }
  27. return ret;
  28. }

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. }
  19. int rmq_max(int L, int R) {
  20. int k = mn[R - L + 1];
  21. return max(stmax[L][k], stmax[R - (1 << k) + 1][k]);
  22. }
  23. int rmq_min(int L, int R) {
  24. int k = mn[R - L + 1];
  25. return min(stmin[L][k], stmin[R - (1 << k) + 1][k]);
  26. }

线段树

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

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

区间增减,区间求和(HDU 1556

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

主席树(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. }
  21. void update(int &x, int last, int l, int r, int pos) {
  22. x = cnt++;
  23. lson[x] = lson[last];
  24. rson[x] = rson[last];
  25. if(l == r) {
  26. Sum[x] = Sum[last] + 1;
  27. return ;
  28. }
  29. int m = (l + r) >> 1;
  30. if(pos <= m) {
  31. update(lson[x], lson[last], l, m, pos);
  32. } else {
  33. update(rson[x], rson[last], m + 1, r, pos);
  34. }
  35. Sum[x] = Sum[lson[x]] + Sum[rson[x]];
  36. }
  37. int query(int L, int R, int l, int r, int k) {
  38. if(l == r) {
  39. return l;
  40. }
  41. int m = (l + r) >> 1;
  42. int tmp = Sum[lson[R]] - Sum[lson[L]];
  43. if(k <= tmp) {
  44. return query(lson[L], lson[R], l, m, k);
  45. } else {
  46. return query(rson[L], rson[R], m + 1, r, k - tmp);
  47. }
  48. }

笛卡尔树(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];
  7. void build(int *num, int nn) {
  8. n = nn;
  9. top = 0;
  10. memset(l, 0, sizeof(int) * (n + 1));
  11. memset(r, 0, sizeof(int) * (n + 1));
  12. memset(vis, 0, sizeof(bool) * (n + 1));
  13. for(int i = 1; i <= n; ++i) {
  14. int tmp = top;
  15. while(top > 0 && num[sta[top - 1]] < num[i]) {
  16. --top;
  17. }
  18. if(top != 0) {
  19. r[sta[top - 1]] = i;
  20. }
  21. if(top < tmp) {
  22. l[i] = sta[top];
  23. }
  24. sta[top++] = i;
  25. }
  26. for(int i = 1; i <= n; ++i) {
  27. vis[l[i]] = vis[r[i]] = true;
  28. }
  29. for(int i = 1; i <= n; ++i) {
  30. if(!vis[i]) {
  31. root = i;
  32. }
  33. }
  34. }
  35. };

莫队

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