网站排名效果好,深圳美食教学网站制作,江西软件职业技术大学,做网站需要多少带宽知识概览
线段树一般有5个操作#xff1a; pushup#xff1a;用子节点更新当前节点信息pushdown#xff1a;把懒标记往下传build#xff1a;初始化一棵树modify#xff1a;修改一个区间query#xff1a;查询一个区间 不带懒标记#xff08;支持单点修改#xff09;的线…知识概览
线段树一般有5个操作 pushup用子节点更新当前节点信息pushdown把懒标记往下传build初始化一棵树modify修改一个区间query查询一个区间 不带懒标记支持单点修改的线段树算法见本人博客
【数据结构】线段树算法总结单点修改-CSDN博客文章浏览阅读81次点赞2次收藏3次。【代码总结】线段树算法总结单点修改https://blog.csdn.net/u012181348/article/details/135119627?spm1001.2014.3001.5501
例题展示
题目链接
243. 一个简单的整数问题2 - AcWing题库https://www.acwing.com/problem/content/244/
代码
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 100010;int n, m;
int w[N];
struct Node
{int l, r;LL sum, add;
} tr[N * 4];void pushup(int u)
{tr[u].sum tr[u 1].sum tr[u 1 | 1].sum;
}void pushdown(int u)
{auto root tr[u], left tr[u 1], right tr[u 1 | 1];if (root.add){left.add root.add, left.sum (LL)(left.r - left.l 1) * root.add;right.add root.add, right.sum (LL)(right.r - right.l 1) * root.add;root.add 0;}
}void build(int u, int l, int r)
{if (l r) tr[u] {l, r, w[r], 0};else{tr[u] {l, r};int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pushup(u);}
}void modify(int u, int l, int r, int d)
{if (tr[u].l l tr[u].r r){tr[u].sum (LL)(tr[u].r - tr[u].l 1) * d;tr[u].add d;}else // 一定要分裂{pushdown(u);int mid tr[u].l tr[u].r 1;if (l mid) modify(u 1, l, r, d);if (r mid) modify(u 1 | 1, l, r, d);pushup(u);}
}LL query(int u, int l, int r)
{if (tr[u].l l tr[u].r r) return tr[u].sum;pushdown(u);int mid tr[u].l tr[u].r 1;LL sum 0;if (l mid) sum query(u 1, l, r);if (r mid) sum query(u 1 | 1, l, r);return sum;
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i) scanf(%d, w[i]);build(1, 1, n);char op[2];int l, r, d;while (m--){scanf(%s%d%d, op, l, r);if (*op C){scanf(%d, d);modify(1, l, r, d);}else printf(%lld\n, query(1, l, r));}return 0;
} 参考资料
AcWing算法提高课
