struct Node
{
　 int data;
　 int addMark;
};
void PushDown(Node* tree,int pos)
{
　 if (tree[pos].addMark == 0) return;
　 tree[pos * 2 + 1].data += tree[pos].addMark;
　 tree[pos * 2 + 2].data += tree[pos].addMark;
　 tree[pos * 2 + 1].addMark += tree[pos].addMark;
　 tree[pos * 2 + 2].addMark += tree[pos].addMark;
　tree[pos].addMark = 0;
}
void BuildTree(Node* tree,int root,int a[],int s,int e)
{
　 if (s + 1 >= e)
　{
　　 tree[root].addMark = 0;
　　 tree[root].data = a[s];
　　 return;
　}
　 int mid = (s + e) / 2;
　BuildTree(tree, 2 * root + 1, a, s, mid);
　BuildTree(tree, 2 * root + 2, a, mid, e);
　tree[root].data = MAX(tree[2 * root + 1].data, tree[2 * root + 2].data);
}
int Query(Node* tree,int root,int s,int e,int qs,int qe)
{
　 if (qe <= s || qs >= e) return -1;
　 if (qs <= s&&qe >= e) return tree[root].data;
　PushDown(tree, root);
　 int mid = (s + e) / 2;
　int lmax=Query(tree, 2 * root + 1, s, mid, qs, qe);
　 int rmax=Query(tree, 2 * root + 1, s, mid, qs, qe);
　return lmax > rmax ? lmax : rmax;
}
void Update(Node* tree,int root,int s,int e,int us,int ue,int v)
{
　 if (ue <= s || us >= e) return;
　if (us >= s&&ue <= e)
　{
　　 tree[root].addMark += v;
　　 tree[root].data += v;
　　return;
　 }
　PushDown(tree, root);
　 int mid = (s + e) / 2;
　Update(tree, 2 * root + 1, s, mid, us, ue,v);
　 Update(tree, 2 * root + 1, s, mid, us, ue,v);
　 tree[root].data = MAX(tree[2 * root + 1].data, tree[2 * root + 2].data);
}

以上线段树用来统计区间最大值，而且采用延迟更新。据说线段树的空间必须开到4n才能保证不溢出。以上代码有一个建树的过程，设想如果线段树节点的值都初始化为0，然后把元素赋值看作更新，就可以省去建树的过程。
线段树当然还有其他的应用，比如统计区间和。有意思的是，在某些特殊的情况下，有其他更简单或效率更高的数据结构来代替线段树。下面有介绍。

树状数组
int LowBit(int x)
{
　 return x&-x;
}
void Add(int tree[],int n,int x, int v)
{
　while (x < n)
　 {
　　tree[x] += v;
　　 x += LowBit(x);
　 }
}
int Sum(int tree[], int x)
{
　 int sum = 0;
　while (x > 0)
　 {
　　sum += tree[x];
　　x -= LowBit(x);
　 }
　return sum;
}

树状数组用来求区间和，从代码量就可以看出，实现非常简单。树状数组维护了一个前缀和，可以实现更新。这里对元素的赋值可以看成更新操作，求区间和就是两个Sum相减。

区间最大值
int a[] = { 0,1,2,3,4,5,6,7,8,9 };
int dp[10][5];
int n = ARRYLEN(a);
void DP()
{
　for (int i = 0; i < n; ++i) dp[i][0] = a[i];
　for (int i = 1; i <= log2(n)+1; ++i)
　{
　 　for (int j = 0; j < n; ++j)
　 　 {
　 　 　 dp[j][i] = dp[j][i - 1];
　 　 　 int index = j + (int)pow(2, i - 1);
　 　 　 if (index < n)
　 　 　 {
　 　 　 　if (dp[index][i - 1] > dp[j][i])
　 　 　 　 　dp[j][i] = dp[index][i - 1];
　 　 　 }
　 　}
　 }
}
int Query(int s, int e)
{
　 int det = e - s;
　int d = (int)log2(det);
　return MAX(dp[s][d],dp[e-(int)pow(2,d)][d]);
}

单调队列
void MonotoneQueue(int a[],int n,int k)
{
　deque<int> queue;
　for (int i = 0; i < n; ++i)
　{
　 　 while (!queue.empty()&&a[queue.back()] < a[i]) queue.pop_back();
　 　 queue.push_back(i);
　 　 if (queue.front() <= i - k) queue.pop_front();
　 　 cout << a[queue.front()] << endl;
　 }
}