CodeVs 1082

传送门 ：线段树练习

线段树 区间修改 + 区间查询

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

 

再接下来一个正整数Q，每行表示操作的个数，

 

如果第一个数是1，后接3个正整数，

 

表示在区间[a,b]内每个数增加X,如果是2，

 

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

线段树区间修改+ 区间查询

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,op,x,y,val;
long long ans;
struct Tree{
	int l;
	int r;
	long long w;
	int f;
}tree[200000*5+100];
void build(int k,int l,int r)
{
	tree[k].l = l;
	tree[k].r = r;
	if(l == r)
	{
		scanf("%d",&tree[k].w);
		return ;
	}
	int m = (tree[k].l + tree[k].r )>>1;
	build(k<<1,l,m);
	build(k<<1|1,m+1,r);
	tree[k].w = tree[k<<1].w + tree[k<<1|1].w;
}
void down(int k)
{
	tree[k<<1].f +=tree[k].f;
	tree[k<<1|1].f+= tree[k].f;
	tree[k<<1].w += (tree[k<<1].r - tree[k<<1].l +1)*tree[k].f;
	tree[k<<1|1].w += (tree[k<<1|1].r - tree[k<<1|1].l+1)*tree[k].f;
	tree[k].f = 0;
}
void add(int k)
{
	if(tree[k].l >=x&&tree[k].r<=y)
	{
		tree[k].w += (tree[k].r - tree[k].l + 1) * val;
		tree[k].f += val;
		return ; 
	}
	if(tree[k].f ) down(k);
	int m = (tree[k].l + tree[k].r)>>1;
	if(x<=m) add(k<<1);
	if(y>m) add(k<<1|1);
	tree[k].w = tree[k<<1].w + tree[k<<1|1].w; 
}
void ask(int k)
{
	if(tree[k].l>=x&&tree[k].r<=y)
	{
		ans += tree[k].w;
		return ;
	}
	if(tree[k].f) down(k);
	int m = (tree[k].l + tree[k].r) >>1;
	if(x<=m) ask(k<<1);
	if(y>m) ask(k<<1|1);
}
int main()
{
	scanf("%d",&n);
	build(1,1,n);
	scanf("%d",&m);
	while(m--)
	{
		
		scanf("%d%d%d",&op,&x,&y);
		if(op == 1)
		{
			scanf("%d",&val);
			add(1);
		}
		else {
			ans = 0;
			ask(1);
			printf("%d\n",ans);
		}
	}
	return 0;
}

ZKW 线段树

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 5;
int n, M;
LL sum[maxn << 2], add[maxn << 2];

void build() {
    M = 1; 
    while(M < (n + 2)) M <<= 1;
    for (int i = 1; i <= n; i++) {
        int x = M + i;
        scanf("%lld", sum + x);
        while(x >>= 1) sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }
}

void update(int l, int r, LL x) {
    l += M - 1, r += M + 1;
    int L = 0, R = 0;
    for (int i = 1; l ^ r ^ 1; i <<= 1, l >>= 1, r >>= 1) {
        sum[l] += L * x, sum[r] += R * x;
        if(~l & 1) add[l ^ 1] += x, sum[l ^ 1] += i * x, L += i;
        if(r & 1)  add[r ^ 1] += x, sum[r ^ 1] += i * x, R += i;
    }
    sum[l] += L * x, sum[r] += R * x;
    while(l >>= 1) sum[l] += x * (L + R);
}

LL query(int l, int r) {
    l += M - 1, r += M + 1;
    LL ans = 0;
    int L = 0, R = 0;
    for (int i = 1; l ^ r ^ 1; i <<= 1, l >>= 1, r >>= 1) {
        ans += add[l] * L + add[r] * R;
        if(~l & 1) ans += sum[l ^ 1], L += i;
        if(r & 1)  ans += sum[r ^ 1], R += i;
    }
    ans += add[l] * L + add[r] * R;
    while(l >>= 1) ans += add[l] * (L + R);
    return ans;
}

int main() {
    scanf("%d", &n);
    build();
    int q;
    scanf("%d", &q);
    while(q--) {
        int op, a, b, c;
        scanf("%d%d%d", &op, &a, &b);
        if(op == 1) {
            scanf("%d", &c);
            update(a, b, c);
        }
        else
            printf("%lld\n", query(a, b));
    }
    return 0;
}

ZKW 线段树 的确比普通线段树要快一点，内存还小

ZKW :    总时间耗费: 661ms        总内存耗费: 7 MB

线段树 ： 总时间耗费: 1059ms      总内存耗费: 13 MB