线段树：
1.求区间最大值（hdu1754）
#include<bits/stdc++.h>
using namespace std;
#define inf 200005
int grade[inf];
struct ndoe{
int l, r, maxn;
}tree[inf<<2];
int bulid(int root, int l, int r){
tree[root].l = l;
tree[root].r = r;
if(l == r) {
return tree[root].maxn = grade[l];
}
int a, b, mid = (l + r)>>1;
a = bulid(root<<1,l,mid);
b = bulid(root<<1|1,mid+1,r);
return tree[root].maxn = max(a,b);
}
int que(int root, int l, int r){
if(tree[root].l > r || tree[root].r < l) {
return 0;
}
if(tree[root].l >= l && tree[root].r <= r) {
return tree[root].maxn;
}
int a, b, mid = (tree[root].l + tree[root].r)>>1;
a = que(root<<1,l,r);
b = que(root<<1|1,l,r);
return max(a,b);
}
void update(int root,int pos,int num){
if(tree[root].l == tree[root].r){
tree[root].maxn = num;
return;
}
int mid = (tree[root].l + tree[root].r)>>1;
if(pos <= mid){
update(root<<1,pos,num);
}else {
update(root<<1|1,pos,num);
}
tree[root].maxn = max(tree[root<<1].maxn,tree[root<<1|1].maxn);
}
int main() {
int n, m;
while(scanf("%d%d",&n,&m)!=EOF) {
memset(grade,0,sizeof(grade));
for(int i = 1; i <= n; i++) {
scanf("%d",&grade[i]);
}
bulid(1,1,n);
getchar();
for(int i = 0; i < m; i++) {
char ch;
scanf("%c",&ch);
int a, b;
if(ch == 'Q'){
scanf("%d%d",&a,&b);
getchar();
printf("%d\n",que(1,a,b));
}else {
scanf("%d%d",&a,&b);
getchar();
update(1,a,b);
}
}
}
return 0;
} 大哥的线段树模板（区间求和）
/*线段数模板*/
//maxn -> 最多节点数
#define maxn 100005
#define ll long long
struct node {
int l,r;
ll sum,lazy;
} tree[maxn * 4]; // 开四倍大小
void push_up(int root) {
tree[root].sum = tree[root << 1].sum + tree[(root << 1) | 1].sum;
} // 儿子的值相加为父亲的值
void push_down(int root) {
if(tree[root].lazy) { //有懒惰值
tree[root << 1].lazy += tree[root].lazy;
tree[(root << 1) | 1].lazy += tree[root].lazy;//向下传递懒惰值
tree[root << 1].sum += tree[root].lazy * (tree[root << 1].r - tree[root << 1].l + 1);
tree[(root << 1) | 1].sum += tree[root].lazy * (tree[(root << 1) | 1].r - tree[(root << 1) | 1].l + 1); //根据题目要求处理
tree[root].lazy = 0;
}
}
void build_tree(int l,int r,int root) {
tree[root].lazy = 0;
tree[root].l = l;
tree[root].r = r;
if(l == r) {
tree[root].sum = 0; // 这里给一个初始值
return ;
}
int mid = (l + r) >> 1;
build_tree(l,mid,root << 1);
build_tree(mid + 1,r,(root << 1) | 1);
push_up(root); //向上更新值
}
//区间l到r 每个点加v
void update_interval(int l,int r,ll v,int root) { //区间更新
if(l <= tree[root].l && r >= tree[root].r) {
tree[root].lazy += v; // 保存懒惰值
tree[root].sum += v * (tree[root].r - tree[root].l + 1);
return ;
}
if(tree[root].lazy)
push_down(root);
int mid = (tree[root].l + tree[root].r) >> 1;
if(l <= mid)
update_interval(l,r,v,root << 1);
if(r > mid)
update_interval(l,r,v,(root << 1) | 1);
push_up(root);
}
int query_interval(int l,int r,int root) { // 区间查询
if(l <= tree[root].l && r >= tree[root].r)
return tree[root].sum;
if(tree[root].lazy) // 查询中遇到未更新的值，进行更新
push_down(root);
int mid = (tree[root].l + tree[root].r) >> 1;
int ans = 0;
if(l <= mid)
ans += query_interval(l,r,root << 1);
if(r > mid)
ans += query_interval(l,r,(root << 1) | 1);
return ans;
}
//点p直接赋值为v
void update_single(int p,ll v,int root) { //单点更新
if(tree[root].l == tree[root].r && tree[root].r == p) {
tree[root].sum = v;
return ;
}
int mid = (tree[root].l + tree[root].r) >> 1;
if(p <= mid)
update_single(p,v,root << 1);
else
update_single(p,v,(root << 1) | 1);
push_up(root); //每个点更新都要向上更新值
}
ll query_single(int p,int root) { //单点查询
if(tree[root].l == tree[root].r && tree[root].r == p) {
return tree[root].sum;
}
if(tree[root].lazy)
push_down(root);
int mid = (tree[root].l + tree[root].r) >> 1;
if(p <= mid)
query_single(p,root << 1);
else
query_single(p,(root << 1) | 1);
} lazy－tag思想，记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
在此通俗的解释我理解的Lazy意思：
现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行更新操作；如果刚好执行到一个rt节点，而且tree[rt].l == a && tree[rt].r == b，这时我们就应该一步更新此时rt节点的sum[rt]的值（sum[rt]+=c* (tree[rt].r - tree[rt].l + 1)）。
关键来了，如果此时按照常规的线段树的update操作，这时候还应该更新rt子节点的sum[]值，而Lazy思想恰恰是暂时不更新rt子节点的sum[]值，而是在这里打一个tag，直接return。直到下次需要用到rt子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间 。
树状数组：
1.单点修改 区间求和（hdu1166）
#include<bits/stdc++.h>
#define maxn 50005
#define lowbit(x) (x & (-x))
using namespace std;
int tree[50005];
int n, t;
void update(int x, int v) {
while(x <= n) {
tree[x] += v;
x += lowbit(x);
}
}
int getsum(int x) {
int ans = 0;
while(x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int getq(int l ,int r) {
int ans = getsum(r) - getsum(l - 1);
return ans;
}
int main() {
int a = 0;
char str[30];
scanf("%d",&t);
while(t--) {
memset(tree, 0, sizeof(tree));
a++;
int k;
scanf("%d",&n);
for(int i =1; i <= n; i++) {
scanf("%d",&k);
update(i, k);
}
printf("Case %d:\n", a);
while(~scanf("%s",str)) {
if(str[0] == 'E') {
break;
}
int i, j;
if(str[0] == 'A') {
scanf("%d%d",&i, &j);
update(i, j);
} else if(str[0] == 'Q') {
scanf("%d%d",&i, &j);
printf("%d\n",getq(i, j));
} else {
scanf("%d%d",&i, &j);
update(i, -j);
}
}
}
return 0;
} 2.树状数组（求逆序数）
//Minimum Inversion Number
#include<cstdio>
#include<cstring>
#define N 5010
using namespace std;
int c[N],n,a[N];
int lowbit(int t) { //计算树状数组t区间管理的a的个数
return t&(-t); //t 二进制数后面k个0，返回值为2^k
}
void updata(int p,int f) { //p在树状数组最先出现的地方是c[p]
while(p <= n) { //将后面所有包含a[p]的树状数组更新
c[p] += f;
p += lowbit(p);
}
}
int getsum(int p) { //求和 a[1] 到 a[p]
int s = 0;
while(p > 0) {
s += c[p]; //c[p] 只管理lowbit(p) 个数
p -= lowbit(p); //那么接下来要算a[1] 到 a[p] - lowbit(p) 的区间和
}
return s;
}
void init() {
for(int i = 0; i <= n; i++) c[i] = 0;
}
int main() {
int i,s,mn;
while(~scanf("%d",&n)) {
init();
s = 0;
for(i = 1; i <= n; i++) {
scanf("%d",&a[i]); //树状数组从下标1开始
s += getsum(n) - getsum(a[i]); //a[i]前面比它大的数，即可生成的倒置数
// printf("s = %d \n",s);
updata(a[i],1); //让所有包含a[i]的树状数组+1
// print();
}
mn = s;
printf("%d\n",mn);
}
return 0;
}
京公网安备 11010502036488号