首页 > 其他分享 >segment_tree

segment_tree

时间:2023-03-24 18:22:05浏览次数:34  
标签:int tr tree mid add 区间 segment ql

这是一棵一棵一棵线段树

众所周知,线段树是一个优质的维护区间信息(需要满足结合律)的数据结构

我们可以

  • \(O(nlogn)\) 建树

  • \(O(logn)\) 查询任意区间的信息

关于结合律:

\[\LARGE(a+b)+c=a+(b+c) \]

so,如何建线段树呢?

首先,我们可以利用结构体封装来解决维护信息较多时的情况

struct Segtr
{
   int l,r;// 线段树此节点维护的区间
   ll sum; // 这个区间的和
   int add; // 懒惰标记
   // lc,rc为左儿子与右儿子,它们所维护的区间分别为[l, mid], [mid + 1, r]
   #define lc (p << 1)
   #define rc (p << 1 | 1)
} tr[N << 2]; // 开4倍空间防止RE

然后就是建树

inline void build(int p, int l, int r)
{
   tr[p].l = l, tr[p].r = r, tr[p].add = 0;
   if (l == r)
   {
       tr[p].sum = a[l]; // a存的是原数据
       return; // 到达叶子节点返回
   }
   int mid = l + r >> 1; // 从中间分开
   build(lc, l, mid); // 建左子树
   build(rc, mid + 1, r); // 建右子树
   pushup(p);
}

\(pushup()\) 函数是合并子区间的函数,具体见下

inline void pushup(int p)
{
   tr[p].sum = tr[lc].sum + tr[rc].sum;
   /* 显而易见,pushup不止可以这样写,在维护区间最大值时
   tr[p].maxn = max(tr[lc].maxn, tr[rc].maxn);
   所以这个函数根据维护值的不同而不同*/
}

接下来,就可以进行区间查询了

inline void query(int p, int ql, int qr) // ql与qr为查询区间,l与r为维护区间
{
   int l = tr[p].l, r = tr[p].r;
   // 这个节点的维护区间被询问区间完全覆盖,那么它所维护的值就一定会对答案产生贡献
   if (ql <= l && qr >= r) return tr[p].sum;
   pushdown(p); // 下传懒惰标记
   int mid = l + r >> 1, ret = 0;
   // query的初始p = 1,也就是说初始维护的区间为[1,n]
   // 对其进行二分,查找符合条件的区间并入ret
   if (ql <= mid) ret += query(lc, ql, qr), ret %= MOD; // 查左树
   if (r > mid) ret += query(rc, ql, qr), ret %= MOD; // 查右树
   return ret;
}

\(pushdown()\) 用于下传懒标,当然只有区间带修时才有用

inline void pushdown(int p)
{
  int l = tr[p].l, r = tr[p].r, mid = l + r >> 1;
  tr[lc].sum += (mid - l + 1) * tr[p].add;
  tr[rc].sum += (r - l) * tr[p].add; // 用标记乘上区间长度为此区间的修改量
  tr[lc].add += tr[p].add;
  tr[rc].add += tr[p].add; // 下传懒标
  tr[p].add = 0;
}

这样就可以愉快的写区修了
单修其实就是让 ql=qr

inline void modify(int p, int ql, int qr, int k)
{
  int l = tr[p].l, r = tr[p].r;
  if (ql <= l && qr >= r) // 完全覆盖
  {
     tr[p].sum += k * (r - l + 1);
     tr[p].add += k;
  }
  pushdown(p);
  int mid = l + r >> 1;
  if (ql <= mid) modify(lc, ql, qr, k); // 递归修改左子树
  if (qr > mid) modify(rc, ql, qr, k); // 递归修改右子树
  pushup(p);
}

于是乎,我们便得到了一棵线段树

标签:int,tr,tree,mid,add,区间,segment,ql
From: https://www.cnblogs.com/cxz-stO/p/17253000.html

相关文章

  • Segment Tree Beats! 初步和其他
    不会渐进表示,全无脑用\(\Theta\)了/kk目录区间最值问题不含区间加减的情况划分数域历史最值问题双半群模型问题描述使用标记维护的问题区间最值问题不含区间加减的......
  • Debunking Rumors on Twitter with Tree Transformer
    Article:l 论文标题:DebunkingRumorsonTwitterwithTreeTransformer(利用树状Transformer模型揭露Twitter中的谣言)l 论文作者:JingMa、WeiGaol 论文来源:2020......
  • Mysql B-Tree与B+Tree区别
    一、B-Tree与B+Tree介绍B-TreeB-Tree是一种平衡树,用于支持快速的查找、插入和删除操作。B-Tree通常被用作关系数据库管理系统(RDBMS)的索引结构,因为它能够在大数据集合中......
  • POJ - 3321 Apple Tree
    原题链接思路答案不好直接维护,所以,我们可以采用DFS序来解决这一问题。设\(l_u\)是以\(u\)为根的子树中最小的时间戳,\(r_u\)是以\(u\)为根的子树中最大的时间戳......
  • 题解 ABC294G【Distance Queries on a Tree】
    DFS序树状数组。不妨以\(1\)为根,设\(\operatorname{dep}(u)\)表示\(u\)到根路径的边权和,\(\operatorname{dis}(u,v)\)表示\(u,v\)间路径的边权和,\(\operatornam......
  • Treemap按key和value降序排序
    Treemap是一种根据键排序的数据结构,可以通过重载它的比较器来按照值排序。要按键排序,可以使用默认的比较器,而要按值排序,可以创建一个自定义的比较器并将其传递给treemap的......
  • Tree Master (根号分治,离散化)
    题目大意:给出一个树,每次给出2个相同高度的点,然后依次向父亲走,问val[a]*val[b]这些值加起来是多少 思路:直接map映射关联容器,时间复杂度过大根号分治?于是......
  • hashmap,hashtabl,hashtree,linkedhashmap区别分析
    java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMapHashtableLinkedHashMap和TreeMap.Map主要用于存储健值对,根据......
  • [CVPR2020] RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clou
    大佬的TensorFlow代码:here另一个大佬的Pytorch代码:等我看完代码再贴链接,之前那个不太行keywords高分辨率点云——约\(10^5\)点云语义分割多层次特征在正式开始......
  • elementUI el-tree setCheckedKeys使用nextTick出现的问题
    [Vuewarn]:ErrorinnextTick:"TypeError:Cannotreadpropertiesofundefined(reading'setCheckedKeys')"TypeError:Cannotreadpropertiesofundefined(read......