tyvj 1038:
同一段序列，对序列询问很多次，用线段树。
第一次写线段树……
先贴上大神给的模板：
// xian duan shu
#include <stdio.h>
#define N 200001
#define max(a,b) a>b?a:b
struct node
{
int l,r;
int maxx;
};
node line[N*3];
int val[N];
void build(int l,int r,int s)
{
line[s].l = l;
line[s].r = r;
if (l == r)
{
line[s].maxx = val[l];
return;
}
int mid = (l+r)>>1;
build(l,mid,s*2);
build(mid+1,r,s*2+1);
line[s].maxx = max(line[s*2].maxx,line[s*2+1].maxx);
}
void modify(int stu, int score, int step)
{//将下标为stu的值修改为score
line[step].maxx = max(line[step].maxx,score);
if (line[step].l == line[step].r)
return;
if (stu > line[step*2].r)
modify(stu, score, step*2+1);
else
modify(stu, score, step*2);
}
int query(int l, int r, int s)
{
if (l == line[s].l && line[s].r == r)
return line[s].maxx;
if (l >= line[s*2+1].l)
return query(l, r, s*2+1);
if (r <= line[s*2].r)
return query(l, r, s*2);
int mid = (line[s].l+line[s].r)>>1;
int ta = query(l, mid, s*2);
int tb = query(mid+1, r, s*2+1);
return max(ta, tb);
}
int main()
{
int n,m;
char str;
int a,b;
while(scanf("%d%d", &n, &m)!=EOF)
{
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
getchar();
build(1,n,1);
while(m--)
{
scanf("%c%d%d", &str, &a, &b);
getchar();
if (str == 'U')
modify(a,b,1);
if (str == 'Q')
printf("%d\n", query(a,b,1));
}
}
}
这题中，每个节点存放的信息是最小值。
其中，查询函数中的if(x >= tree[s * 2 + 1].l) 表示的是如果要查询的区间左边界比右孩子的左边界大或者等于，那么就到右孩子中继续查询。
if(y <= tree[s * 2].r)表示如果要查询的区间的右边界比左孩子的右边界小或者等于，那么就到左孩子中继续查询。
#include <stdio.h>
#include <string.h>
struct node
{
int l, r, min;
//左边界，右边界，边界中的最小值
};
node tree[100010 * 3];
int a[100010];
int build(int ll, int rr, int s)
{//左边界，右边界，当前要创建的节点在tree数组中下标
int i;
tree[s].l = ll;
tree[s].r = rr;
if(ll == rr)
{
tree[s].min = a[ll];
return tree[s].min;
}
int mid = (ll + rr) / 2;
int t1 = build(ll, mid, s * 2);
int t2 = build(mid + 1, rr, s * 2 + 1);
tree[s].min = t1 < t2 ? t1 : t2;
return tree[s].min;
}
int search(int x, int y, int s)
{
if(x == tree[s].l && y == tree[s].r)
return tree[s].min;
if(x >= tree[s * 2 + 1].l)//注意这两个条件，之前一直错在这
return search(x, y, s * 2 + 1);
if(y <= tree[s * 2].r)//注意
return search(x, y, s * 2);
//如果搜索的范围跨越了两个孩子，那么就在左孩子中找[x，mid]的最小值，
//在右孩子中找[mid + 1，y]的最小值，再从两个返回的最小值中选择小的
int mid = (tree[s].l + tree[s].r) / 2;//注意不是(x + y) / 2
int t1 = search(x, mid, s * 2);
int t2 = search(mid + 1, y, s * 2 + 1);
return t1 > t2 ? t2 : t1;
}
int main (void)
{
int m, n;
scanf("%d %d", &m, &n);
int i;
for(i = 1; i <= m; i++)
scanf("%d", &a[i]);
int ok = build(1, m, 1);//从下标1开始存储
//for(i = 1; i < m * 2; i++)
// printf("l = %d, r = %d, min = %d\n", tree[i].l, tree[i].r, tree[i].min);
int a, b;
for(i = 0; i < n; i++)
{
scanf("%d %d", &a, &b);
printf("%d\n", search(a, b, 1));
}
return 0;
}
nyoj 116：
结点存的信息是区间里所有数的总和， 比上面那题多了一个修改
#include <stdio.h>
struct node
{
int l, r, sum;
};
node tree[1000010 * 2];
int sol[1000010];
int build(int ll, int rr, int s)
{
tree[s].l = ll;
tree[s].r = rr;
if(ll == rr)
{
tree[s].sum = sol[ll];
return tree[s].sum;
}
int mid = (ll + rr) / 2;
int s1 = build(ll, mid, s * 2);
int s2 = build(mid + 1, rr, s * 2 + 1);
tree[s].sum = s1 + s2;//左孩子和右孩子的数值的总和
return tree[s].sum;
}
int search(int ll, int rr, int s)
{
int ss = 0;
if(ll == tree[s].l && rr == tree[s].r)
return tree[s].sum;
if(ll >= tree[s * 2 + 1].l)
return search(ll, rr, s * 2 + 1);
if(rr <= tree[s * 2].r)
return search(ll, rr, s * 2);
int mid = (tree[s].l + tree[s].r) / 2;
ss += search(ll, mid, s * 2);
ss += search(mid + 1, rr, s * 2 + 1);
return ss;
}
void modify(int a, int b, int s)
{
tree[s].sum += b;
if(tree[s].l == tree[s].r)
{
//tree[s].sum += b;之前这里多加了一遍……
return ;
}
if(a >= tree[s * 2 + 1].l)
modify(a, b, s * 2 + 1);
if(a <= tree[s * 2].r)
modify(a, b, s * 2);
}
int main (void)
{
int n, m, i;
while(scanf("%d %d", &n, &m) != EOF)
{
getchar();
for(i = 1; i <= n; i++)
scanf("%d",&sol[i]);
int ok = build(1, n, 1);
//for(i = 1; i < n * 2; i++)
// printf("l = %d, r = %d, sum = %d\n", tree[i].l, tree[i].r, tree[i].sum);
char s[6];
int a, b;
for(i = 0; i < m; i++)
{
scanf("%s%d%d", s, &a, &b);
getchar();
if(s[0] == 'Q')
printf("%d\n", search(a, b, 1));
else
{
modify(a, b, 1);
// for(int j = 1; j < n * 2; j++)
//printf("l = %d, r = %d, sum = %d\n", tree[j].l, tree[j].r, tree[j].sum);
}
}
}
return 0;
}