首页 > 代码库 > 线段树模板1
线段树模板1
题目见洛谷P3372
已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和
简单来说就是需要支持区间修改(区间加)和区间查询。
(貌似也可以用分块和树状数组水过的样子,虽然我暂时并不知道树状数组是怎么做到的(嗯,以后一定会学的))
因为数据范围long long的问题一直70分....
代码如下:
#include <iostream> #include <cstdio> using namespace std; const int maxn=200010; int m, n, f, a[maxn]; long long sumv[maxn<<2], addv[maxn<<2]; void build_tree(int o, int L, int R) { if (L==R) addv[o]=sumv[o]=a[L]; else { int M=L+((R-L)>>1); int lc=(o<<1), rc=((o<<1)+1); build_tree(lc, L, M); build_tree(rc, M+1, R); sumv[o]=sumv[lc]+sumv[rc]; } return; } int yl, yr; long long query(int o, int L, int R, long long add) { if (yl<=L && R<=yr) return sumv[o]+add*(R-L+1); int M=L+((R-L)>>1); long long sum=0; int lc=(o<<1), rc=((o<<1)+1); if (yl<=M) sum+=query(lc, L, M, add+addv[o]); if (yr>M) sum+=query(rc, M+1, R, add+addv[o]); return sum; } void maintain(int o, int L, int R) { int lc=(o<<1), rc=((o<<1)+1); sumv[o]=addv[o]*(R-L+1); if (R>L) sumv[o]+=sumv[lc]+sumv[rc]; return; } int ql, qr; int v; void update(int o, int L, int R) { if (ql<=L && R<=qr) addv[o]+=v; else { int M=L+((R-L)>>1); int lc=(o<<1), rc=((o<<1)+1); if (ql<=M) update(lc, L, M); if (qr>M) update(rc, M+1, R); } maintain(o, L, R); return; } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) scanf("%d", &a[i]); build_tree(1, 1, n); while (m--){ scanf("%d", &f); if (f==1) { scanf("%d%d%d", &ql, &qr, &v); update(1, 1, n); } else { scanf("%d%d", &yl, &yr); printf("%lld\n",query(1, 1, n, 0)); } } return 0; }
线段树模板1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。