算法-线段树

• 线段树
• • 单点更新 区间查询
  • • 1. 2021-4-9 hdu1166 求区间和
    • 2. 2021-4-9 hdu1754 求区间最大值

线段树

线段树原理

单点更新 区间查询

1. 2021-4-9 hdu1166 求区间和

hdu1166

思路

最简单的单点更新，区间查询，用的是非递归的做法。
容易出错的点有<<1和<<2的区别。
如何识别一行的字符串和多个int呢，可以通过char ch[10],int a,int b。
scanf(%s%d%d)实现。
另外本题读到End是要break的，但不需要再输入a和b。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int A[maxn];
int sum[maxn << 2];
int add[maxn << 2];
int n, N;
void build()
{
    N = 1; while (N < n + 2)N <<= 1;
    for (int i = 1; i <= n; ++i)sum[i + N] = A[i];
    for (int i = N - 1; i; --i)
    {
        sum[i] = sum[i << 1] + sum[i << 1 | 1];
        add[i] = 0;
    }
    
}
void update(int L, int C)
{
    for (int s = L + N; s; s >>= 1)
    {
        sum[s] += C;
    }
}
int query(int L, int R)
{
    int ans = 0;
    for (int s = L + N - 1, t = R + N + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
    {
        if (~s & 1) { ans += sum[s ^ 1]; }
        if (t & 1) { ans += sum[t ^ 1]; }
    }
    return ans;
}
int main()
{
    int T; scanf("%d", &T); int i = 1;
    while (T--)
    {
        memset(A, 0, sizeof(A));
        memset(sum, 0, sizeof(sum));
        memset(add, 0, sizeof(add));
        printf("Case %d:\n", i++);
        scanf("%d", &n);
        for(int i=1;i<=n;++i)scanf("%d", &A[i]);
        build();
        char ch[10];
        while (~scanf("%s", ch))
        {
            if (ch[0] == 'Q')
            {
                int a, b;
                scanf("%d%d", &a, &b);
                printf("%d\n", query(a, b));
            }
            else if (ch[0] == 'A')
            {
                int a, b;
                scanf("%d%d", &a, &b);
                update(a, b);
            }
            else if (ch[0] == 'S')
            {
                int a, b;
                scanf("%d%d", &a, &b);
                b *= -1;
                update(a, b);
            }
            else if (ch[0] == 'E')
            {
                break;
            }
        }
    }
    return 0;
}

2. 2021-4-9 hdu1754 求区间最大值

hdu1754

思路

和求区间和不同的是，此题每次更改某个位置的值。那么先要通过Max[L+N]=C,然后更新父节点。
父节点每次取左孩子和右孩子的最大值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int A[maxn];
int Max[maxn << 2];
int add[maxn << 2];
int n,m, N;
void build()
{
    N = 1; while (N < n + 2)N <<= 1;
    for (int i = 1; i <= n; ++i)Max[i + N] = A[i];
    for (int i = N - 1; i; --i)
    {
        Max[i] =max(Max[i << 1], Max[i << 1 | 1]) ;
        add[i] = 0;
    }
    
}
void update(int L, int C)
{
    Max[L + N] = C;
    for (int s = (L + N)>>1; s; s >>= 1)
    {
        Max[s] = max(Max[s << 1], Max[s << 1 | 1]);
    }
}
int query(int L, int R)
{
    int ans = 0;
    for (int s = L + N - 1, t = R + N + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
    {
        if (~s & 1) { ans = max(ans, Max[s ^ 1]); }
        if (t & 1) { ans = max(ans, Max[t ^ 1]); }
    }
    return ans;
}
int main()
{ 
    while (~scanf("%d%d", &n,&m))
    {
        memset(A, 0, sizeof(A));
        memset(Max, 0, sizeof(Max));
        memset(add, 0, sizeof(add));
        for (int i = 1; i <= n; ++i)scanf("%d", &A[i]);
        char ch[10]; int a, b;
        build();
        while (m--)
        {
            scanf("%s%d%d", ch, &a, &b);
            if (ch[0] == 'Q')
            {
                printf("%d\n", query(a, b));
            }
            else
            {
                update(a, b);
            }
        }
    }
    return 0;
}