• 可持续化线段树（主席树）几种用法总结

    1.权值主席树

    Acwing255. 第K小数icon-default.png?t=M666https://www.acwing.com/problem/content/257/

    最经典的主席树用法，使用主席树来避免建立多个具有重复结点的权值线段树，直接通过不同版本间的信息维护出区间的最大最小值。

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define int long long
    12. #define endl '\n'
    13. #define lowbit(x) (x) &(-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void TLE(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);}
    19. const int N = 2e5 + 10;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int n, m;
    27. int a[N];
    28. int root[N];
    29. struct node
    30. {
    31.     int l, r;
    32.     int cnt;
    33. }t[N*40];
    34. int idx;
    35. vector<int> alls;
    36. int id(int x)
    37. {
    38.     return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
    39. }
    40. int build(int l,int r)
    41. {
    42.     int q = ++idx;
    43.     if (l==r)
    44.         return q;
    45.     int mid = l + r >> 1;
    46.     t[q].l = build(l, mid), t[q].r = build(mid + 1, r);
    47.     return q;
    48. }
    49. int insert(int p,int l,int r,int x)
    50. {
    51.     int q = ++idx;
    52.     t[q] = t[p];
    53.     if(l==r)
    54.     {
    55.         t[q].cnt++;
    56.         return q;
    57.     }
    58.     int mid = l + r >> 1;
    59.     if(x<=mid)
    60.         t[q].l = insert(t[p].l, l, mid, x);
    61.     else
    62.         t[q].r = insert(t[p].r, mid + 1, r, x);
    63.     t[q].cnt = t[t[q].l].cnt + t[t[q].r].cnt;
    64.     return q;
    65. }
    66. int query(int q,int p,int l,int r,int k)
    67. {
    68.     if(l==r)
    69.         return l;
    70.     int cnt = t[t[q].l].cnt - t[t[p].l].cnt;
    71.     int mid = l + r >> 1;
    72.     if(cnt>=k)
    73.         return query(t[q].l, t[p].l, l, mid, k);
    74.     else
    75.         return query(t[q].r, t[p].r, mid + 1, r, k-cnt);
    76. }
    77. signed main()
    78. {
    79.     scanf("%lld%lld", &n, &m);
    80.     for (int i = 1; i <= n;i++)
    81.     {
    82.         scanf("%lld", &a[i]);
    83.         alls.push_back(a[i]);
    84.     }
    85.     sort(alls.begin(), alls.end());
    86.     alls.erase(unique(alls.begin(), alls.end()), alls.end());
    87.     root[0] = build(0, alls.size()-1);
    88.     for (int i = 1; i <= n;i++)
    89.         root[i] = insert(root[i - 1], 0, alls.size()-1, id(a[i]));
    90.     while(m--)
    91.     {
    92.         int l, r, k;
    93.         scanf("%lld%lld%lld", &l, &r, &k);
    94.         printf("%lld\n", alls[query(root[r], root[l - 1], 0, alls.size()-1, k)]);
    95.     }
    96. }

    2.单个历史版本修改主席树

    P3919 【模板】可持久化线段树 1（可持久化数组）icon-default.png?t=M666https://www.luogu.com.cn/problem/P3919

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. //#define int long long
    12. #define endl '\n'
    13. #define lowbit(x) (x) & (-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void TLE() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
    19. const int N = 2e6 + 10;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int n, m, idx;
    27. int a[N];
    28. int root[N];
    29. struct node
    30. {
    31.     int l, r;
    32.     int val;
    33. } t[N * 20];
    34. int build(int l, int r)
    35. {
    36.     int q = ++idx;
    37.     if (l == r)
    38.     {
    39.         t[q].val = a[l];
    40.         return q;
    41.     }
    42.     int mid = l + r >> 1;
    43.     t[q].l = build(l, mid), t[q].r = build(mid + 1, r);
    44.     return q;
    45. }
    46. int modify(int p, int l, int r, int k, int x)
    47. {
    48.     int q = ++idx;
    49.     t[q] = t[p];
    50.     if (l == r)
    51.     {
    52.         t[q].val = x;
    53.         return q;
    54.     }
    55.     int mid = l + r >> 1;
    56.     if (k <= mid)
    57.         t[q].l = modify(t[p].l, l, mid, k, x);
    58.     else
    59.         t[q].r = modify(t[p].r, mid + 1, r, k, x);
    60.     return q;
    61. }
    62.  
    63. int query(int p, int l, int r, int k)
    64. {
    65.     if (l == r)
    66.     {
    67.         return t[p].val;
    68.     }
    69.     int mid = l + r >> 1;
    70.     if (k <= mid)
    71.         return query(t[p].l, l, mid, k);
    72.     else
    73.         return query(t[p].r, mid + 1, r, k);
    74. }
    75.  
    76. int main()
    77. {
    78.     scanf("%d%d", &n, &m);
    79.     for (int i = 1; i <= n; i++)
    80.     {
    81.         scanf("%d", &a[i]);
    82.     }
    83.     root[0] = build(1, n);
    84.     int cnt = 0;
    85.     while (m--)
    86.     {
    87.         int v, op, loc, val;
    88.         scanf("%d%d%d", &v, &op, &loc);
    89.         if (op == 1)
    90.         {
    91.             scanf("%d", &val);
    92.             root[++cnt] = modify(root[v], 1, n, loc, val);
    93.         }
    94.         else
    95.         {
    96.             root[++cnt] = root[v];
    97.             printf("%d\n",query(root[v], 1, n, loc));
    98.         }
    99.     }
    100. }

    3.这里记录一种不用初始建树的建树方法

    P1383 高级打字机icon-default.png?t=M666https://www.luogu.com.cn/problem/P1383

    这种方法很类似与普通线段树的开点方法，不过要对每一个版本的线段树都要维护一个代表当前版本线段树已存元素个数的len值，在树上进行二分开点。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #define int long long
    12. #define endl '\n'
    13. #define lowbit(x) (x) & (-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void TLE() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
    19. const int N = 2e5 + 10;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int root[N], idx;
    27. int len[N];
    28. struct node
    29. {
    30.     int l, r;
    31.     char v;
    32. } t[N * 20];
    33. int insert(int p, int l, int r, int f, char v)
    34. {
    35.     int q = ++idx;
    36.     t[q] = t[p];
    37.     if (l == r)
    38.     {
    39.         t[q].v = v;
    40.         return q;
    41.     }
    42.     int mid = l + r >> 1;
    43.     if (f <= mid)
    44.         t[q].l = insert(t[p].l, l, mid, f, v);
    45.     else
    46.         t[q].r = insert(t[p].r, mid + 1, r, f, v);
    47.     return q;
    48. }
    49.  
    50. char query(int p, int l, int r, int f)
    51. {
    52.     if (l == r)
    53.         return t[p].v;
    54.     int mid = l + r >> 1;
    55.     if (f <= mid)
    56.         return query(t[p].l, l, mid, f);
    57.     else
    58.         return query(t[p].r, mid + 1, r, f);
    59. }
    60.  
    61. signed main()
    62. {
    63.     TLE();
    64.     int n;
    65.     cin >> n;
    66.     int cnt = 0;
    67.     for (int i = 1; i <= n; i++)
    68.     {
    69.         char op[2], c[2];
    70.         int x;
    71.         cin >> op;
    72.         if (*op == 'T')
    73.         {
    74.             cin >> c;
    75.             ++cnt;
    76.             len[cnt] = len[cnt - 1] + 1;
    77.             root[cnt] = insert(root[cnt - 1], 1, n, len[cnt], *c);
    78.         }
    79.         else if (*op == 'Q')
    80.         {
    81.             cin >> x;
    82.             cout << query(root[cnt], 1, n, x) << endl;
    83.         }
    84.         else if (*op == 'U')
    85.         {
    86.             cin >> x;
    87.             ++cnt;
    88.             root[cnt] = root[cnt - x - 1]; 
    89.             len[cnt] = len[cnt - x - 1];
    90.         }
    91.     }
    92.     return 0;
    93. }

  • 相关阅读:
    记一次EDU证书站
    Intellij IDEA 运行时报 Command line is too long
    各种框架的面试
    Android13 按键kl文件优先级详解
    进程的虚拟地址空间
    国庆周《重点回顾LINUX第五课》
    手机端出现Z-Fighting现象
    Java笔记：垃圾回收
    JAVA信息技术共享社区计算机毕业设计Mybatis+系统+数据库+调试部署
    开源数据库postgresql在统信系统上的离线安装shell脚本
  • 原文地址：https://blog.csdn.net/Bookerbobo/article/details/126236292