# Luogu P3374 [template] tree array 1 (CDQ divide and conquer)

## Title Description

For example, if you know a sequence, you need to do the following two operations:

1. Add a number to x

2. Find the sum of each number in a certain interval

## I / O format

Input format:

The first row contains two integers, N and M, which respectively represent the number of numbers and the total number of operations in the sequence.

The second line contains N integers separated by spaces, where the i-th number represents the initial value of the i-th item in the sequence.

Next, each row of row M contains three integers, representing an operation, as follows:

Operation 1: Format: 1 x k meaning: add the x-th number to K

Operation 2: Format: 2 x y meaning: sum of each number in the output range [x,y]

Output format:

The output contains several line integers, which are the results of all operations 2.

## Example of input and output

Input example ා 1:copy
```5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4```
Output example:copy
```14
16```

## explain

Space time limit: 1000ms,128M

Data size:

For 30% data: n < = 8, m < = 10

For 70% of data: n < = 10000, m < = 10000

For 100% data: n < = 500000, m < = 500000

Example description:

So output results 14, 16

CDQ divide and conquer maintain two-dimensional partial order

The first dimension is sorted out

The second dimension is divided by CDQ

Slow to death..

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<ctime>
5 #include<cstdlib>
6 using namespace std;
7 #define ls T[now].ch[0]
8 #define rs T[now].ch[1]
9 const int MAXN=2*1e6+10;
10 inline char nc()
11 {
12     static char buf[MAXN],*p1=buf,*p2=buf;
14 }
16 {
17     char c=nc();int x=0,f=1;
18     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
19     while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
20     return x*f;
21 }
22 int n,m;
23 struct node
24 {
25     int idx;//Number of inquiries
26     int val;//Modified value
27     int type;//Operation type
28     bool operator<( const node &a) const {
29         return idx==a.idx?type<a.type:idx<a.idx;}
30 }Q[MAXN];
31 int qidx=0;//Number of operations
32 int aidx=0;//Number of queries
33 int ans[MAXN];
34 node tmp[MAXN];
35 void CDQ(int l,int r)
36 {
37     if(r-l<=1)    return ;
38     int mid=(l+r)>>1;CDQ(l,mid);CDQ(mid,r);
39     int sum=0;
40     int p=l,q=mid,o=0;
41     while(p<mid&&q<r)
42     {
43         if(Q[p]<Q[q])
44         {
45             if(Q[p].type==1) sum+=Q[p].val;
46             tmp[o++]=Q[p++];
47         }
48         else
49         {
50             if( Q[q].type==2)    ans[Q[q].val]-=sum;
51             else if(Q[q].type==3)    ans[Q[q].val]+=sum;
52             tmp[o++]=Q[q++];
53         }
54     }
55     while(p<mid) tmp[o++]=Q[p++];
56     while(q<r)
57     {
58         if( Q[q].type==2)    ans[Q[q].val]-=sum;
59         else if(Q[q].type==3)    ans[Q[q].val]+=sum;
60         tmp[o++]=Q[q++];
61     }
62     for(int i=0;i<o;i++) Q[i+l]=tmp[i];
63 }
64 int main()
65 {
66     #ifdef WIN32
67     freopen("a.in","r",stdin);
68     #else
69     #endif
71     for(int i=1;i<=n;i++)
72     {
73         Q[qidx].idx=i;
74         Q[qidx].type=1;
76     }
77     for(int i=0;i<m;i++)
78     {
80         Q[qidx].type=type;
82         else
83         {