HDU 1166 【线段树 || 树状数组，单点修改 维护区间和】

题目链接 HDU 1166

大概题意：

第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令

思路：类似于区间查询和区间修改等操作，操作数又较多的情况优先想线段树、树状数组等。而线段树和树状数组的相似之处在于二分思想的应用，不同的是前者直接二分，后者要转换为二进制间接对数组以一种特定的组合形式进行二分。

方法一：线段树，因为线段树又是一颗平衡二叉树，所以可以用二叉树的构建方法，在这里用的是结构数组的表示方法。

结点 ：T[a, b] （a, b 表示区间 [a, b] , 其中 b-a 为长度 len ）

线段树递归定义为：

若 len > 1 ， 则 [a, (a+b)/2] 为 T 的左儿子， [(a+b)/2+1, b] 为 T 的右儿子。

若 len == 1， 则 T 为叶子节点。

复杂度：

线段树的深度不超过log2len， 线段树把区间上的任意一条线段都分成不超过 2log2len 条线段。所以线段树能在O（log2len) 时间内完成一条线段的插入， 删除， 和查找等工作。

入门题，AC code：

///HDU 1166 线段树

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

struct

{

    int a, b, sum;  ///左端点， 右端点， 区间和

}t[140000];

int people[50010], SUM;   ///每个营地的人数

void make(int x, int y, int num)  ///x为左端点，y为右端点，num为数组下标

{

    t[num].a = x;  ///确定左端点为x

    t[num].b = y;  ///确定右端点为y

    if(x == y)     ///左端点等于右端点，说明到达叶子结点

        t[num].sum = people[y];

    else

    {

        make(x, (x+y)/2, num+num); ///递归构造左子树

        make((x+y)/2+1, y, num+num+1); ///递归构造右子树

        t[num].sum = t[num+num].sum + t[num+num+1].sum;

        ///父结点的区间和等于子树的区间和之和，因为区间被分成两半

    }

}

void add(int i, int j, int num) ///第i个堡垒加j艘船，初始nun为1，即从根结点开始

{

    t[num].sum+=j;

    if(t[num].a == i && t[num].b == i) ///找到叶子结点，返回

        return;

    if(i > (t[num].a+t[num].b)/2) ///点i在该区间的右边

        add(i, j, num+num+1);     ///递归进右结点

    else

        add(i, j, num+num);       ///否则递归进左结点

}

void sub(int i, int j, int num) ///第i个堡垒减j艘船

{

    t[num].sum-=j;

    if(t[num].a == i && t[num].b == i) ///找到叶子结点，返回

        return;

    if(i > (t[num].a+t[num].b)/2)

        sub(i, j, num+num+1);

    else

        sub(i, j, num+num);

}

void query(int i, int j, int num)    ///求i到j的总飞船长度， num初始化为1，即从根节点开始

{

    if(i <= t[num].a && j >= t[num].b)

        SUM+=t[num].sum;

    else

    {

        int mid = (t[num].a + t[num].b)/2;

        if(i > mid)

            query(i, j, num+num+1);

        else if(j <= mid)

            query(i, j, num+num);

        else

        {

            query(i, j, num+num);

            query(i, j, num+num+1);

        }

    }

}

int main()

{

    int N, T;

    char command[6];

    scanf("%d", &T);

    int j = 0;

    while(T--)

    {

        int temp, a, b;

        scanf("%d", &N);

        for(int i = 1; i <= N; i++)

        {

            scanf("%d", &people[i]);

        }

        make(1, N, 1);

        printf("Case %d:\n", ++j);

        while(cin >> command)

        {

            if(strcmp(command, "End") == 0) break;

            else if(strcmp(command, "Query") == 0)

            {

                cin >> a >> b;

                SUM = 0;

                query(a, b, 1);

                cout << SUM << endl;

            }

            else if(strcmp(command, "Add") == 0)

            {

                cin >> a >> b;

                add(a, b, 1);

            }

            else if(strcmp(command, "Sub") == 0)

            {

                cin >> a >> b;

                sub(a, b, 1);

            }

        }

    }

    return 0;

}

　　

方法二：树状数组

关键在于二进制下的二分思想，理解通过 lowbit （求最低位1）进行数组关系的递推。

Ac code：

///HDU 1166 树状数组

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int MAXN = 50005;

int N;

int c[MAXN]; ///树状数组

int lowbit(int x)     ///位运算，取最低位1，用于后面树状数组下标的二分

{

    return x&(-x);

}

void add(int i, int value)   ///单点加，由上自下更新树状数组

{

    while(i <= N)

    {

        c[i]+=value;

        //printf("%d %d\n", i, c[i]);

        i+=lowbit(i);

    }

}

int sum(int i)      ///求前缀和

{

    int sum = 0;

    while(i > 0)

    {

        sum+=c[i];

        i-=lowbit(i);

    }

    return sum;

}

int main()

{

    int T;

    char command[6];

    scanf("%d", &T);

    int j = 0;

    while(T--)

    {

        int temp, a, b, d;

        scanf("%d", &N);

        memset(c, 0, sizeof(c));

        for(int i = 1; i <= N; i++)

        {

            scanf("%d", &d);

            add(i, d);

        }

        ///debug

        /*

        for(int i = 1; i <= N; i++)

            printf("%d ", c[i]);

        puts("");

        */

        printf("Case %d:\n", ++j);

        while(cin >> command)

        {

            if(strcmp(command, "End") == 0) break;

            else if(strcmp(command, "Query") == 0)

            {

                cin >> a >> b;

                int SUM = 0;

                SUM = sum(b) - sum(a-1);

                cout << SUM << endl;

            }

            else if(strcmp(command, "Add") == 0)

            {

                cin >> a >> b;

                add(a, b);

            }

            else if(strcmp(command, "Sub") == 0)

            {

                cin >> a >> b;

                add(a, -b);

            }

        }

    }

    return 0;

}

　　

HDU 1166 【线段树 || 树状数组，单点修改 维护区间和】的相关教程结束。