codevs1080 第一次用ZKW线段树

Posted by Cww97 on 2016-01-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50474962
题目描述 Description

一行N个方格,开始每个格子里都有一个整数。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子区间[a,b]中所有元素的和;修改的规则是指定某一个格子x,加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000,,提问和修改的总数m<10000条。

输入描述 Input Description
输入文件第一行为一个整数N,接下来是n行n个整数,表示格子中原来的整数。接下一个正整数m,再接下来有m行,表示m个询问,第一个整数表示询问代号,询问代号1表示增加,后面的两个数x和A表示给位置X上的数值增加A,询问代号2表示区间求和,后面两个整数表示a和b,表示要求[a,b]之间的区间和。
输出描述 Output Description
共m行,每个整数

样例输入 Sample Input
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6

样例输出 Sample Output
22
22

数据范围及提示 Data Size & Hint
1≤N≤100000, m≤10000 。

仅仅存个代码

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
program cx;
const hk:array[1..30]of longint=(2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824);
var i,n,m,BTM,x,y,z:longint; //BTM:主任的变量名
a:array[0..500000]of longint;

procedure change(x,d:longint); //只要单点修改
begin
x:=x+BTM;
repeat
a[x]:=a[x]+d;
x:=x >> 1 ;
until x=0;
end;

function query(l,r:longint):longint; //不要在意这些细节
var ans:longint;
begin
ans:=0;
l:=l+BTM-1; r:=r+BTM+1;
while not(l xor r=1) do
begin
if l and 1=0 then inc(ans,a[l xor 1]);
if r and 1=1 then inc(ans,a[r xor 1]);
l:=l >> 1; r:=r >> 1;
end;
exit(ans);
end;

begin
//assign(input, 'hk.in'); reset(input);
//assign(output,'hk.out'); rewrite(output);
read(n);
BTM:=1;
while BTM<=n do BTM:=BTM << 1 ;
for i:=1 to 30 do if hk[i]=n then BTM:=BTM >> 1;
dec(BTM);
for i:=1 to n do read(a[i+BTM]);
for i:=BTM-1 downto 1 do a[i]:=a[i << 1]+a[i << 1 xor 1];
read(m);
for i:=1 to m do
begin
read(x,y,z);
if x=1 then change(y,z)
else writeln(query(y,z));
end;
//close(input);
//close(output);
end.

第一次上codevs的时候

这里写图片描述
这里写图片描述