当前位置: 首页 > news >正文

线段树

很早之前就学过线段树,但是一直觉得麻烦,没有写过。
今天根据AI的代码,用类封装了一个使用起来还算简单的线段树,方便自己记忆。

class SegmentTree
{vector<int> tree;vector<int> arr;vector<int> lazy;int n;void build(int p,int l,int r){if(l==r){tree[p] = arr[l];return;}int mid = (l+r)/2, lch = p*2, rch = p*2+1;build(lch,l,mid);build(rch,mid+1,r);tree[p] = tree[lch] + tree[rch];}void push_down(int p,int l,int r){if(lazy[p]==0)return;int mid = (l+r)/2, lch = p*2, rch = p*2+1;tree[lch] += lazy[p] * (mid-l+1);lazy[lch] += lazy[p];tree[rch] += lazy[p] * (r-mid);lazy[rch] += lazy[p];lazy[p] = 0;}void update(int p,int l,int r,int ul,int ur,int k){if(l>=ul && r<=ur){lazy[p] += k;tree[p] += k*(r-l+1);return;}push_down(p,l,r);int mid = (l+r)/2, lch = p*2, rch = p*2+1;if(ul<=mid) update(lch,l,mid,ul,ur,k);if(ur>mid) update(rch,mid+1,r,ul,ur,k);tree[p] = tree[lch] + tree[rch];}int query(int p,int l,int r,int ul,int ur){if(ul>r || ur<l)return 0;if(l>=ul && r<=ur)return tree[p];push_down(p,l,r);int mid = (l+r)/2, lch = p*2, rch = p*2+1;return query(lch,l,mid,ul,ur) + query(rch,mid+1,r,ul,ur);}public:SegmentTree(vector<int> &input){n = input.size();tree.resize(4*n);lazy.resize(4*n);arr.resize(n);for(int i=0;i<n;i++)arr[i] = input[i];build(1,0,n-1);}void update(int l,int r,int k){update(1,0,n-1,l,r,k);}int query(int l,int r){return query(1,0,n-1,l,r);}
};

简单说一下这样写的优势有哪些吧。
1.方便记忆。
因为封装在类里,所以每次要写的代码都是一样的,不用根据不同的数组名写不同的代码。
2.方便调用
在public里我定义了调用时用到的函数,减少了p,l,r这几个参数,在主函数里调用的时候就不用想那么多了。
3.不易冲突
如果定义在全局变量,代码功能不仅线段树,可能会和其他部分有冲突。封装在类里,就不会有这个风险。

http://www.hskmm.com/?act=detail&tid=12103

相关文章:

  • CSP-S模拟24
  • 今年CSP...
  • 0voice-2.1.1-io多路复用select/poll/epoll
  • Transformer与ViT
  • comfUI背后的技术——VAE - 实践
  • CCPC2023 秦皇岛 M. Inverted
  • redux
  • 20250921 模拟赛 T4 题解
  • 1.3 课前问题列表
  • NOIP 模拟赛十一
  • Proxy 库解析(四)
  • warm-flow 监听器对象获取问题
  • Hexo Butterfly 5.4 分页问题 YAML 错误 解决方法总结
  • js逆向:某Q音乐平台请求数据模拟生成
  • maven
  • 第十一届中国大学生程序设计竞赛网络预选赛(CCPC Online 2025)
  • 网络流
  • 完整教程:数据结构 栈和队列、树
  • 深入解析:【ubuntu】ubuntu中找不到串口设备问题排查
  • 酵母双杂交技术:高通量筛选的突破与不可忽视的三大局限性
  • ubuntu20.04测试cuda
  • Android Studio 配置国内源
  • PyCharm项目上传GitHub仓库(笔记) - 教程
  • 从RAG出发
  • 软件工程第二次作业——第一次个人编程作业
  • Ubuntu 24.04 安装 DaVinci Resolve
  • Promise中处理请求超时问题
  • 图解26:老生常谈的OSI网络模型
  • 【C++】指针
  • AI驱动建筑行业数字化转型