FilesExpand file tree

master

/

segmentTree.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (62 loc) · 1.37 KB

master

/

segmentTree.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (62 loc) · 1.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#include <bits/stdc++.h>

using namespace std;

#define mx 100005

int arr[mx],tree[3*mx];

void init(int i, int tl, int tr){

if(tl==tr) tree[i]=arr[tl];

else {

int tm=(tl+tr)/2;

init(2*i,tl,tm);

init(2*i+1,tm+1,tr);

tree[i]=tree[2*i]+tree[2*i+1];

}

}

void update(int i, int tl, int tr, int key, int value){

if(tl>tr) return;

else if(tl==tr && tl==key) tree[i]=0;

else {

int tm=(tl+tr)/2;

if(key<=tm)

update(2*i,tl,min(tm,tr),key,value);

else

update(2*i+1,max(tm+1,tl),tr,key,value);

tree[i]=tree[2*i]+tree[2*i+1];

}

}

int query(int i, int tl, int tr, int L, int R){

if(L>R) return 0;

else if(tl==L && tr==R) return tree[i];

int tm=(tl+tr)/2;

return query(2*i,tl,tm,L,min(R,tm))

+query(2*i+1,tm+1,tr,max(L,tm+1),R);

}

int main(){

int tcase;

scanf("%d",&tcase);

for(int kase=1;kase<=tcase;kase++){

memset(arr,0,sizeof arr);

memset(tree,0,sizeof tree);

printf("Case %d:\n",kase);

int n,q;

scanf("%d%d",&n,&q);

for(int i=0;i<n;i++)

scanf("%d",&arr[i]);

init(1,0,n-1);

for(int i=1;i<=q;i++){

int a;

scanf("%d",&a);

if(a==1){

int b;

scanf("%d",&b);

printf("%d\n",query(1,0,n-1,b,b));

update(1,0,n-1,b,0);

} else{

int b,c;

scanf("%d%d",&b,&c);

if(a==2) update(1,0,n-1,b,c);

else printf("%d\n",query(1,0,n-1,b,c));

}

}

}

return 0;

}