有啥必要写zkw呢,树状数组不好嘛QAQ
by yijan @ 2019-07-13 11:03:55
就是想学学
技多不压身嘛对吧
by lacunes @ 2019-07-13 11:05:00
普通线段树就能过吧...
by SSerxhs @ 2019-07-13 11:05:20
是吗,我的这个貌似TLE了第二个点,julao能帮我看看是什么原因吗
**感谢**
by lacunes @ 2019-07-13 11:07:18
@[lacunes](/space/show?uid=179007) 不会zkw,告辞
by SSerxhs @ 2019-07-13 11:08:59
(⊙o⊙)…
by lacunes @ 2019-07-13 11:09:34
@[lacunes](/space/show?uid=179007) 重口味线段树拓展性不强,还是学普通的比较好,方便可持久化
by Void_struct @ 2019-07-13 12:31:11
@[Gary_Fang](/space/show?uid=213500)
想了一中午想通了
,感谢
by lacunes @ 2019-07-13 14:06:56
我写的ZKW
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
int n, m, arr[N];
struct ZKW_SegmentTree
{
int sum[N<<4],M;
#define lc rot<<1
#define rc rot<<1^1
void Build()
{
M = (1 << (int)(log2(n))) - 1;
memset(sum, 0, sizeof(sum));
for(int j = 1,i = 1 + M; i <= n + M; i++,j++)
{
//scanf("%d ",&sum[i]);
sum[i] = arr[j];
}
for(int rot = M; rot >= 1; rot--)
{
sum[rot] = sum[lc] + sum[rc];
}
}
void Add(int rot, int x)
{
sum[rot+=M] += x;
for(rot>>=1; rot; rot>>=1)
{
sum[rot] = sum[lc] + sum[rc];
}
}
int Enquiry(int l, int r)
{
int ans = 0;
for(l += M-1, r += M+1; l^r^1; l>>=1, r>>=1)
{
if(~ l & 1) ans += sum[l^1];
if( r & 1) ans += sum[r^1];
}
return ans;
}
}T;
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",&arr[i]);
if(1 << (int)log2(n) != n) n = 1 << ((int)log2(n) + 1);
T.Build();
for(int flag, tmp1, tmp2, i = 0; i < m; i++)
{
scanf("%d %d %d", &flag, &tmp1, &tmp2);
if(flag == 1)
T.Add(tmp1, tmp2);
else if(flag == 2)
printf("%d\n", T.Enquiry(tmp1, tmp2));
}
return 0;
}
```
by 违规用户名98971 @ 2019-07-30 12:40:25