线段树基础模块

线段树（1）

线段树如图，图要记清楚，就是一棵饱和二叉树，最后一排没有画的的也存在，只是没有值，所以左节点为2u,右节点为2u+1，所以对于区间【1，n】,结构体数组应为4n.

对于线段树基础，有几个主要的模块。

1，建立线段树（初始Build（））

 1 void build(int u,int left,int right)
 2 {
 3     node[u].l=left;
 4     node[u].r=right;
 5     node[u].add=0;
 6     if(node[u].l==node[u].r)
 7     {
 8         node[u].sum=a[left];
 9         return ;//叶子节点 
10     }
11     int mid=(left+right)>>1;
12     build(u*2,left,mid);
13     build(u*2+1,mid+1,right);
14     Pushup(u);//只赋值了叶子节点，向上更新 
15 }

2，更新操作（加一个值，乘一个字Updata()）

 1 void updata(int u,int left,int right,int ad)
 2 {
 3     if(node[u].l==left&&node[u].r==right)
 4     {
 5         node[u].add+=ad;//有些还没有pushdouwn的.add要加上去一起更新 
 6         node[u].sum+=(right-left+1)*ad;
 7         return; 
 8     }
 9     node[u].sum+=(right-left+1)*ad;//u节点区间包含[left,right],也要加上
10     if(node[u].add)pushdown(u);//延时向下更新 
11     int mid=(node[u].l+node[u].r)>>1;
12     if(right<=mid)updata(u*2,left,right,ad);
13     else if(left>mid)updata(u*2+1,left,right,ad);//若左右边都有，分成两段计算 
14     else 
15     {
16         updata(u*2,left,mid,ad);
17         updata(u*2+1,mid+1,right,ad);//同时占有左右子树，把他分成两部分计算 
18     }
19     // pushup(u);因为有node[u].sum+=(right-left+1)*ad;
20 }

3，查询（一段区间的和Query（））

 1 long long Query(int u,int left,int right)
 2 {
 3     if(node[u].l==left&&node[u].r==right)
 4     return node[u].sum;
 5     if(node[u].add)pushdown(u);//add不为0，说明还未更新，查询就要顺便向下更新(便于延时更新)
 6     int mid=(node[u].l+node[u].r)>>1;
 7     if(right<=mid)return Query(u*2,left,right);
 8     else if(left>mid)return Query(u*2+1,left,right);
 9     else 
10         return (Query(u*2,left,mid)+Query(u*2+1,mid+1,right));
11         
12     //pushup(u);//同理 
13 }

4，向上回溯（Pushup（））

1 void Pushup(int u)
2 {
3     node[u].sum=node[u*2].sum+node[u*2+1].sum;
4     return ;
5 }

5，向下延时更新（Pushdown（））----为什么是延时，看下面

1 void pushdown(int u)
2 {
3     node[u*2].add+=node[u].add;
4     node[u*2].sum+=(node[u*2].r-node[u*2].l+1)*node[u].add;
5     node[u*2+1].add+=node[u].add;
6     node[u*2+1].sum+=(node[u*2+1].r-node[u*2+1].l+1)*node[u].add;
7     node[u].add=0;//加完就清0，说明已经更新过了 
8 }

poj 3468 A Simple Problem with Integers（线段树）

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

  1 #include<iostream>
  2 #include<cstdio>
  3 #define N 100005
  4 using namespace std;
  5 int n,m;
  6 int a[N];
  7 struct Node
  8 {
  9     int l,r;//节点所包含的左右区间端点 
 10     long long sum;
 11     long long add;//add是指每个所增加的（即为C） 
 12 }node[4*N];
 13 void Pushup(int u)
 14 {
 15     node[u].sum=node[u*2].sum+node[u*2+1].sum;
 16     return ;
 17 } 
 18 void pushdown(int u)
 19 {
 20     node[u*2].add+=node[u].add;
 21     node[u*2].sum+=(node[u*2].r-node[u*2].l+1)*node[u].add;
 22     node[u*2+1].add+=node[u].add;
 23     node[u*2+1].sum+=(node[u*2+1].r-node[u*2+1].l+1)*node[u].add;
 24     node[u].add=0;//加完就清0，说明已经更新过了 
 25 }
 26 void build(int u,int left,int right)
 27 {
 28     node[u].l=left;
 29     node[u].r=right;
 30     node[u].add=0;
 31     if(node[u].l==node[u].r)
 32     {
 33         node[u].sum=a[left];
 34         return ;//叶子节点 
 35     }
 36     int mid=(left+right)>>1;
 37     build(u*2,left,mid);
 38     build(u*2+1,mid+1,right);
 39     Pushup(u);//只赋值了叶子节点，向上更新 
 40 }
 41 void updata(int u,int left,int right,int ad)
 42 {
 43     if(node[u].l==left&&node[u].r==right)
 44     {
 45         node[u].add+=ad;//有些还没有pushdouwn的.add要加上去一起更新 
 46         node[u].sum+=(right-left+1)*ad;
 47         return; 
 48     }
 49     node[u].sum+=(right-left+1)*ad;//u节点区间包含[left,right],也要加上
 50     if(node[u].add)pushdown(u);//延时向下更新 
 51     int mid=(node[u].l+node[u].r)>>1;
 52     if(right<=mid)updata(u*2,left,right,ad);
 53     else if(left>mid)updata(u*2+1,left,right,ad);//若左右边都有，分成两段计算 
 54     else 
 55     {
 56         updata(u*2,left,mid,ad);
 57         updata(u*2+1,mid+1,right,ad);//同时占有左右子树，把他分成两部分计算 
 58     }
 59     // pushup(u);因为有node[u].sum+=(right-left+1)*ad;
 60 }
 61 long long Query(int u,int left,int right)
 62 {
 63     if(node[u].l==left&&node[u].r==right)
 64     return node[u].sum;
 65     if(node[u].add)pushdown(u);//add不为0，说明还未更新，查询就要顺便向下更新
 66     int mid=(node[u].l+node[u].r)>>1;
 67     if(right<=mid)return Query(u*2,left,right);
 68     else if(left>mid)return Query(u*2+1,left,right);
 69     else 
 70         return (Query(u*2,left,mid)+Query(u*2+1,mid+1,right));
 71         
 72     //pushup(u);//同理 
 73 } 
 74 int main()
 75 {
 76     freopen("POJ3468.in","r",stdin);
 77     freopen("POJ3468.out","w",stdout);
 78     while((scanf("%d%d",&n,&m))==2)
 79     {
 80         for(int i=1;i<=n;i++)
 81     scanf("%d",&a[i]);
 82     getchar();
 83     build(1,1,n);
 84     for(int i=1;i<=m;i++)
 85     {
 86         int x,y,z;
 87         char c;
 88         scanf("%c ",&c);
 89         if(c=='Q')
 90         {
 91             scanf("%d%d",&x,&y);
 92             long long w=Query(1,x,y);
 93             cout<<w<<endl;
 94             getchar();
 95         }
 96         if(c=='C')
 97         {
 98             scanf("%d%d%d",&x,&y,&z);
 99             updata(1,x,y,z);
100             getchar();
101         }
102         
103     } 
104     }
105     
106     return 0;
107 }