最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

线段树

来源：博客园


(资料图片仅供参考)

代码思路

主体部分：

初始化，修改，查询（即build，update，query三个函数）三者的逻辑基本都是：判断是否到达（被完全覆盖）\(\longrightarrow\)消除标记\(\longrightarrow\)二分递归\(\longrightarrow\)返回答案。

辅助部分：

区间值维护，打懒标记，消懒标记（即push_up，add_tag，push_down三个函数）

简化部分：

自定义数据类型，左右儿子自助计算（struct Tree，ls&rs函数）

原理（极简）

树+分块=线段树，无尽的二分递归

代码注释

#include using namespace std;#define ll long long// 区间修改，区间查询，区间和 const int N = 4e6+5; // 数据范围，建议x4，多开不上当，多开不吃亏ll a[N], tree[N], tag[N];int ls(int p){return p << 1;} // 左儿子int rs(int p){return p<<1|1;} // 右儿子void push_up(int p){    tree[p] = tree[ls(p)] + tree[rs(p)];} // 维护区间值（运算可根据题意变动，如求最大值等）void build(int p, int pl, int pr){ // 初始化    tag[p] = 0; // 懒运算标记（lazy_tag）    if(pl == pr){tree[p] = a[pl]; return ;}    // 若已经走到了最底层，则根据原数列赋值    int mid = (pl+pr)>>1; // 将当前区间“平均地”分为两块    build(ls(p), pl, mid); // 左    build(rs(p), mid+1, pr); // 右    push_up(p); // 计算区间值}void add_tag(int p, int pl, int pr, ll d){    tag[p] += d; // 更新懒运算标记（add_lazy_tag）    tree[p] += d*(pr-pl+1); // 更新区间值，记得要算区间内所有数的变动}void push_down(int p, int pl, int pr){ // 把懒标记转移到子树    if(!tag[p]) return ;    int mid = (pl+pr)>>1; // 一分为二（梅开二度）    add_tag(ls(p), pl, mid, tag[p]); // 左    add_tag(rs(p), mid+1, pr, tag[p]); // 右    tag[p] = 0; // 消除标记}void update(int l, int r, int p, int pl, int pr, ll d){ // 区间修改（[l,r]+d）    if(l <= pl && r >= pr){ // 如果被完全覆盖        add_tag(p, pl, pr, d); // 打上懒标记（等到之后不能完全覆盖的时候用）        return ; // 不用跑子树    }    push_down(p, pl, pr); // 不能完全覆盖：先把懒标记传下去（懒标记一定是完全覆盖的）    int mid = (pl+pr)>>1; // 一分为二（梅花三弄）    if(l <= mid) update(l, r, ls(p), pl, mid, d); // 如果左边被（部分）覆盖    if(r > mid) update(l, r, rs(p), mid+1, pr, d); // 如果右边被（部分）覆盖    push_up(p); // 子树已经更新完，用儿子的值维护当前区间值}ll query(int l, int r, int p, int pl, int pr){ // 区间查询（[l,r]）    if(l <= pl && r >= pr) return tree[p]; // 如果被完全覆盖：返回区间值    push_down(p, pl, pr); // 不能完全覆盖，：为了保证值是最新的，传递懒标记    ll ret = 0; // 返回值：统计左、右区间被覆盖部分合并后的值    int mid = (pl+pr)>>1; // 一分为二（大四喜）    if(l <= mid) ret += query(l, r, ls(p), pl, mid); // 如果左边被（部分）覆盖    if(r > mid) ret += query(l, r, rs(p), mid+1, pr); // 如果右边被（部分）覆盖    return ret; // 返回答案}int main(){    int n, m; // 原数列长为n，对其有m次操作    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++)        scanf("%lld", &a[i]); // 输入原数列    build(1, 1, n); // 建树（根节点编号为1,代表了[1,n]的区间范围）    for(int i = 1; i <= m; i++){        int type, l, r; ll d;        scanf("%d", &type); // 操作类别        if(type == 1){ // type[1]:修改区间[l,r]中的数，使其值加d            scanf("%d%d%lld", &l, &r, &d);            update(l, r, 1, 1, n, d);        }        if(type == 2){ // type[2]：输出区间[l,r]的区间和            scanf("%d%d", &l, &r);            printf("%lld\n", query(l, r, 1, 1, n));        }    }    return 0;}

关键词：