• 线段树--

    此前分析过树状数组，这两者具有解决相似问题的共同点。但线段树的功能更加强大，可以说，能用树状数组解决的问题，用线段树都可以解决，然而反之不成立。

    目录

    线段树1

    线段树2

    线段树打标记1

    线段树打标记2

    线段树1

    focus：

            树状数组修改单点时，要修改原数组，因为原数组会被再次用到，而线段树则可以不用修改，因为原数组没有被再次使用，使用的都是seg线段数组（如果原数组会被再次使用，则也要修改）

            重载了 + 运算符

            体现封装的特性，好维护和拓展

    1. // problem :  
    2.  
    3. #include 
    4. using namespace std;
    5. #define ll long long
    6. typedef pair<int, int> PII;
    7. #define pb push_back
    8. const int N = 2e5 + 5;
    9. int n, q, a[N];
    10. struct info {
    11.     int minv, mincnt;
    12. };
    13. info operator + (const info &l, const info &r) {
    14.     info a;
    15.     a.minv = min(l.minv, r.minv);
    16.     if(l.minv < r.minv)a.mincnt = l.mincnt;
    17.     else if(l.minv > r.minv)a.mincnt = r.mincnt;
    18.     else a.mincnt = l.mincnt + r.mincnt;
    19.     return a;
    20. }
    21. struct node {
    22.     info val;
    23. }seg[N * 4];
    24.  
    25. void update(int id) {
    26.     seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
    27. }
    28. void build(int id, int l, int r){
    29.     if(l == r) {
    30.         seg[id].val = {a[l], 1};
    31.     } else {
    32.         int mid = (l + r) / 2;
    33.         build(id * 2, l, mid);
    34.         build(id * 2 + 1, mid + 1, r);
    35.         update(id);
    36.     }
    37. }
    38.  
    39. void change(int id, int l, int r, int pos, int val) {
    40.     if(l == r) {
    41.         seg[id].val = {val, 1};
    42.     } else {
    43.         int mid = (l + r) / 2;
    44.         if(pos <= mid) change(id * 2, l, mid, pos, val);
    45.         else change(id * 2 + 1, mid + 1, r, pos, val);
    46.         update(id);
    47.     }
    48. }
    49.  
    50. info query(int id, int l, int r, int ql, int qr) {
    51.     if(ql == l && qr == r) {
    52.         return seg[id].val;
    53.     }
    54.     int mid = (l + r) / 2;
    55.     if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    56.     else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    57.     else return query(id * 2, l, mid, ql, mid) +
    58.         query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    59. }
    60. int main(){
    61.     scanf("%d %d", &n, &q);
    62.     for(int i = 1; i <= n; ++i)
    63.         scanf("%d", &a[i]);
    64.     build(1, 1, n);
    65.     while(q--) {
    66.         int ty; scanf("%d", &ty);
    67.         if(ty == 1) {
    68.             int pos, val; scanf("%d %d", &pos, &val);
    69.             change(1, 1, n, pos, val);
    70.         } else {
    71.             int l, r; scanf("%d %d", &l, &r);
    72.             info ans = query(1, 1, n, l, r);
    73.             printf("%d %d\n", ans.minv, ans.mincnt);
    74.         }
    75.     }
    76.  
    77.     return 0;
    78. }

     

    线段树2

    一般求最大字段和可以通过贪心来求解，直接for一遍数组。但显然，这题n*q明显会时间超限。 

    solve：

            复用上一题的代码（这就是封装的好处！！！） 但有些太简单的问题，就不要封装。

            只需修改线段数组中保存的信息，以及重载运算的方式即可。

    focus：

            a 为父节点保存的信息，   l 为其左孩子保存的信息，r为右孩子保存的信息

            mss: max segment sum

            mpre  :  max prefix

            msuf  :  max sufix

            s  : sum

            信息具体怎么维护看代码

     

    1. // problem :  
    2.  
    3. #include 
    4. using namespace std;
    5. #define ll long long
    6. typedef pair<int, int> PII;
    7. #define pb push_back
    8. const int N = 2e5 + 5;
    9. int n, q, a[N];
    10. struct info {
    11.     ll mss, mpre, msuf, s;
    12.     info(){}
    13.     info(int val):mss(val), mpre(val), msuf(val), s(val){}
    14. };
    15. info operator + (const info &l, const info &r) {
    16.     info a;
    17.     a.mss = max({l.mss, r.mss, l.msuf + r.mpre});
    18.     a.mpre = max(l.mpre, l.s + r.mpre);
    19.     a.msuf = max(r.msuf, r.s + l.msuf);
    20.     a.s = l.s + r.s;
    21.     return a;
    22. }
    23. struct node {
    24.     info val;
    25. }seg[N * 4];
    26.  
    27. void update(int id) {
    28.     seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
    29. }
    30. void build(int id, int l, int r){
    31.     if(l == r) {
    32.         seg[id].val = info(a[l]);
    33.     } else {
    34.         int mid = (l + r) / 2;
    35.         build(id * 2, l, mid);
    36.         build(id * 2 + 1, mid + 1, r);
    37.         update(id);
    38.     }
    39. }
    40.  
    41. void change(int id, int l, int r, int pos, int val) {
    42.     if(l == r) {
    43.         seg[id].val = info(val);
    44.     } else {
    45.         int mid = (l + r) / 2;
    46.         if(pos <= mid) change(id * 2, l, mid, pos, val);
    47.         else change(id * 2 + 1, mid + 1, r, pos, val);
    48.         update(id);
    49.     }
    50. }
    51.  
    52. info query(int id, int l, int r, int ql, int qr) {
    53.     if(ql == l && qr == r) {
    54.         return seg[id].val;
    55.     }
    56.     int mid = (l + r) / 2;
    57.     if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    58.     else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    59.     else return query(id * 2, l, mid, ql, mid) +
    60.         query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    61. }
    62. int main(){
    63.     scanf("%d %d", &n, &q);
    64.     for(int i = 1; i <= n; ++i)
    65.         scanf("%d", &a[i]);
    66.     build(1, 1, n);
    67.     while(q--) {
    68.         int ty; scanf("%d", &ty);
    69.         if(ty == 1) {
    70.             int pos, val; scanf("%d %d", &pos, &val);
    71.             change(1, 1, n, pos, val);
    72.         } else {
    73.             int l, r; scanf("%d %d", &l, &r);
    74.             info ans = query(1, 1, n, l, r);
    75.             printf("%lld\n", ans.mss);
    76.         }
    77.     }
    78.  
    79.     return 0;
    80. }

    线段树打标记1

     focus：

            update(id)    id编号的子树发生了变化，所以更新id这个节点的信息

            settag(id)   给id这个节点打标记，   打标记的同时，节点的信息发生变化

            pushdown(id)   将id节点的标记下传给子节点

    注意tag要开ll ，  因为标记可能叠加，（不着急传到子节点）

    1. // problem :  
    2.  
    3. #include 
    4. using namespace std;
    5. #define ll long long
    6. typedef pair<int, int> PII;
    7. #define pb push_back
    8. const int N = 2E5 + 5;
    9. int n, q, a[N];
    10. struct node {
    11.     ll t, val;
    12. }seg[N * 4];
    13.  
    14. void update(int id) {
    15.     seg[id].val = max(seg[id * 2].val, seg[id * 2 + 1].val);
    16. }
    17. void build(int id, int l, int r) {
    18.     if(l == r){
    19.         seg[id].val = a[l];
    20.     } else {
    21.         int mid = (l + r) / 2;
    22.         build(id * 2, l, mid);
    23.         build(id * 2 + 1, mid + 1, r);
    24.         update(id);
    25.     }
    26. }
    27. void settag(int id, ll t) {
    28.     seg[id].val += t;
    29.     seg[id].t += t;
    30. }
    31.  
    32. void pushdown(int id) {
    33.     if(seg[id].t) {
    34.         settag(id * 2, seg[id].t);
    35.         settag(id * 2 + 1, seg[id].t);
    36.         seg[id].t = 0;
    37.     }
    38. }
    39. void modify(int id, int l, int r, int ql, int qr, int t) {
    40.     if(l == ql && r == qr) {
    41.         settag(id, t);
    42.         return;
    43.     }
    44.     pushdown(id);
    45.     int mid = (l + r) / 2;
    46.     if(qr <= mid) modify(id * 2, l, mid, ql, qr, t);
    47.     else if(ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    48.     else modify(id * 2, l, mid, ql, mid, t),
    49.         modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    50.     update(id);
    51. }
    52.  
    53. ll query(int id, int l, int r, int ql, int qr) {
    54.     if(l == ql && r == qr) {
    55.         return seg[id].val;
    56.     }
    57.     pushdown(id);
    58.     int mid = (l + r) / 2;
    59.     if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    60.     else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    61.     else return max(query(id * 2, l, mid, ql, mid),
    62.         query(id * 2 + 1, mid + 1, r, mid + 1, qr));
    63. }
    64. int main(){
    65.     scanf("%d %d", &n, &q);
    66.     for(int i = 1; i <= n; ++i)
    67.         scanf("%d", &a[i]);
    68.     build(1, 1, n);
    69.     while(q--) {
    70.         int ty; scanf("%d", &ty);
    71.         if(ty == 1) {
    72.             int l, r, t;
    73.             scanf("%d %d %d", &l, &r, &t);
    74.             modify(1, 1, n, l, r, t);
    75.         } else {
    76.             int l, r; scanf("%d %d", &l, &r);
    77.             printf("%lld\n", query(1, 1, n, l, r));
    78.         }
    79.     }
    80.  
    81.     return 0;
    82. }

    线段树打标记2

     按常理来说，要有多个标记。但是多个标记太麻烦了，而且还要考虑先后顺序。所以就萌发出一种合并这3个标记的想法 。

    focus：

            标记怎么合并？

            怎么根据合并后的标记对区间和进行更新

    struct tag {
        ll mul, add;
    };

    +d         -->         {1,d}

    *d         -->          {d,0}

    变成d       --->     {0, d}    为什么这里是令所有的ai 变为d呢  ？     

    看代码的settag部分。起始时，tag的每个tag的初始状态为(1,0)   mul变为0，则说明ai为0，要再变成d，那add部分为d就好了。   真的神奇。

    1. // problem :  
    2.  
    3. #include 
    4. using namespace std;
    5. #define ll long long
    6. typedef pair<int, int> PII;
    7. #define pb push_back
    8. const int N = 2E5 + 5;
    9. int n, q, a[N];
    10. const int mod = 1e9 + 7;
    11.  
    12. struct tag {
    13.     ll mul, add;
    14. };
    15. tag operator + (const tag &t1, const tag &t2) {
    16.     // (mul1 + add1) * mul2 + add2;
    17.     return {t1.mul * t2.mul % mod, (t1.add * t2.mul % mod + t2.add) % mod}; 
    18. }
    19. struct node {
    20.     tag t;
    21.     ll val;
    22.     int sz;
    23. }seg[N * 4];
    24.  
    25.  
    26. void update(int id) {
    27.     seg[id].val = (seg[id * 2].val + seg[id * 2 + 1].val) % mod;
    28. }
    29. void build(int id, int l, int r) {
    30.     seg[id].t = (tag){1, 0};
    31.     seg[id].sz = r - l + 1;
    32.     if(l == r){
    33.         seg[id].val = a[l];
    34.     } else {
    35.         int mid = (l + r) / 2;
    36.         build(id * 2, l, mid);
    37.         build(id * 2 + 1, mid + 1, r);
    38.         update(id);
    39.     }
    40. }
    41. void settag(int id, tag t) {
    42.     seg[id].val = seg[id].val * t.mul % mod + seg[id].sz * t.add % mod;
    43.     seg[id].t = seg[id].t + t;
    44. }
    45.  
    46. void pushdown(int id) {
    47.     if(seg[id].t.mul != 1 || seg[id].t.add != 0) {
    48.         settag(id * 2, seg[id].t);
    49.         settag(id * 2 + 1, seg[id].t);
    50.         seg[id].t.mul = 1;
    51.         seg[id].t.add = 0;
    52.     }
    53. }
    54. void modify(int id, int l, int r, int ql, int qr, tag t) {
    55.     if(l == ql && r == qr) {
    56.         settag(id, t);
    57.         return;
    58.     }
    59.     pushdown(id);
    60.     int mid = (l + r) / 2;
    61.     if(qr <= mid) modify(id * 2, l, mid, ql, qr, t);
    62.     else if(ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    63.     else modify(id * 2, l, mid, ql, mid, t),
    64.         modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    65.     update(id);
    66. }
    67.  
    68. ll query(int id, int l, int r, int ql, int qr) {
    69.     if(l == ql && r == qr) {
    70.         return seg[id].val;
    71.     }
    72.     pushdown(id);
    73.     int mid = (l + r) / 2;
    74.     if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    75.     else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    76.     else return (query(id * 2, l, mid, ql, mid) +
    77.         query(id * 2 + 1, mid + 1, r, mid + 1, qr)) % mod;
    78. }
    79. int main(){
    80.     scanf("%d %d", &n, &q);
    81.     for(int i = 1; i <= n; ++i)
    82.         scanf("%d", &a[i]);
    83.     build(1, 1, n);
    84.     while(q--) {
    85.         int ty; scanf("%d", &ty);
    86.         if(ty <= 3) {
    87.             int l, r, d;
    88.             scanf("%d %d %d", &l, &r, &d);
    89.             if(ty == 1) modify(1, 1, n, l, r, (tag){1, d});
    90.             else if (ty == 2) modify(1, 1, n, l, r, (tag){d, 0});
    91.             else modify(1, 1, n, l, r, (tag){0, d});
    92.         } else {
    93.             int l, r; scanf("%d %d", &l, &r);
    94.             printf("%lld\n", query(1, 1, n, l, r));
    95.         }
    96.     }
    97.  
    98.     return 0;
    99. }

  • 相关阅读:
    贪心（区间问题 Huffman树 排序不等式 绝对值不等式 推公式）
    后端程序员推荐——接口Mock工具json-server
    初识_JDK代理cglib代理_1
    2019 CSP-S1 模拟赛3-模拟测试题
    图像质量评估——PSNR：峰值信噪比和SSIM：结构相似性（纯手撸代码）
    2023年天津财经大学珠江学院专升本报名缴费准考证下载考试须知
    不使用脚手架构建vue项目
    HCIA-R&S自用笔记（26）PPP
    DBCO-PEG-OPSS/OPSS-PEG-DBCO/二苯并环辛炔聚乙二醇修饰邻吡啶二硫
    为什么处理有序的数组比无序的数组更快
  • 原文地址：https://blog.csdn.net/PURSUE__LIFE/article/details/125910379