By

文章目录

小心越界

每次在修改节点的sum值时，如果每次都下放到叶子节点，那么复杂度会变成nlogn，还不如直接暴力（树状数组还sqrt（n）呢，虽然我不会），而且对于某些修改一大段值的问题，用线段树动态维护的时候，如果找到了要修改的大区间，可以直接在这个大区间上标记，然后改掉sum值，等下次修改或者查询时再修改或者查询它的标记值，这样就可以做到每次查询或修改都为logn，大大节省了时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 #include<cstdlib>
 #include<iostream>
 #include<cstring>
 #include<cstdio>
 #define ll(x) ((x)<<1)
 #define rr(x) ((x)<<1|1)
using namespace std;
struct Node
{
int left;
int right;
__int64 value;//这里注意
int add;//标记，提高时间效率
}tree[300000];
int num[100010];
__int64 build(int l,int r,int idx)
{
int mid;
tree[idx].left=l;
tree[idx].right=r;
tree[idx].add=0;
if(l==r)
{
return tree[idx].value=num[l];//叶子节点值
}
mid=(l+r)/2;
return tree[idx].value=build(l,mid,ll(idx))+build(mid+1,r,rr(idx));//又忘了加1，囧事
}
__int64 query(int l,int r,int idx)
{
int mid;
if(tree[idx].left==l&&tree[idx].right==r)
return tree[idx].value;//
if(tree[idx].add)//接着更新，这里易错
{
tree[ll(idx)].value+=(__int64)(tree[ll(idx)].right-tree[ll(idx)].left+1)*tree[idx].add;
tree[rr(idx)].value+=(__int64)(tree[rr(idx)].right-tree[rr(idx)].left+1)*tree[idx].add;
tree[ll(idx)].add+=tree[idx].add;
tree[rr(idx)].add+=tree[idx].add;
tree[idx].add=0;
}
mid=(tree[idx].left+tree[idx].right)/2;
if(r<=mid)
return query(l,r,ll(idx));
else if(l>mid)
return query(l,r,rr(idx));
else
return query(l,mid,ll(idx))+query(mid+1,r,rr(idx));//一直忘记+1；
}
void update(int l,int r,int a,int idx)
{
int mid;
if(tree[idx].left>=l&&tree[idx].right<=r)
{
tree[idx].value+=(__int64)(tree[idx].right-tree[idx].left+1)*a;
tree[idx].add+=a;
return ;//以为这里没有更新孩子节点，所以在query中还有更新的环节
}
if(tree[idx].add)//接着更新，这里易错
{
tree[ll(idx)].value+=(__int64)(tree[ll(idx)].right-tree[ll(idx)].left+1)*tree[idx].add;
tree[rr(idx)].value+=(__int64)(tree[rr(idx)].right-tree[rr(idx)].left+1)*tree[idx].add;
tree[ll(idx)].add+=tree[idx].add;
tree[rr(idx)].add+=tree[idx].add;
tree[idx].add=0;
}
mid=(tree[idx].left+tree[idx].right)/2;
if(l<=mid)
update(l,r,a,ll(idx));//只要有一个就得更新
if(r>mid)
update(l,r,a,rr(idx));
tree[idx].value=tree[ll(idx)].value+tree[rr(idx)].value;
}
int main()
{
int i,m,n,l,r;
int a;
char ch[10];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)//这里下标从1开始
scanf("%d",&num[i]);
build(1,n,1);
while(m--)
{
getchar();
cin>>ch;
//scanf("%s",ch);
if(ch[0]=='Q')
{
scanf("%d%d",&l,&r);
printf("%I64d\n",query(l,r,1));//防止越界
}
else
{
scanf("%d%d%d",&l,&r,&a);
update(l,r,a,1);
}
}
}
return 0;
}
文章目录