海战（线段树）- HDU 4027

这一篇是典型的线段树算法，这个算法在日常工作中可能非常少见，因为可以被常规算法所取代，但是在问题达到一定数量级之后，常规算法是很难搞定类似问题的，可以说线段树是高级算法中非常低调的一种，也许在某些关键时刻能让你化险为夷。

线段树简单的说就是对一个序列每次从中间划分为2个区间，然后依次划分子区间。如图：

先看下维基百科的说明：

线段树（英语：Segment tree）是一种二叉树形数据结构，1977年由Jon Louis Bentley发明[1]，用以储存区间或线段，并且允许快速查询结构内包含某一点的所有区间。

一个包含n个区间的线段树，空间复杂度O(nlogn)，查询的时间复杂度则O(logn+k)，其中k是符合条件的区间数量。

此数据结构亦可推广到高维度。

本处以一维的线段树为例。

线段树结构示意，其储存的线段显示在图片的下方。

令S是一维线段的集合。将这些线段的端点坐标由小到大排序，令其为x1,x2,...xn。我们将被这些端点切分的每一个区间称为“单位区间”（每个端点所在的位置会单独成为一个单位区间），从左到右包含：

• 线段树的结构为一个二叉树，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：
• 其每一个叶节点，从左到右代表每个单位区间。
• 其内部节点代表的区间是其两个儿子代表的区间之联集。
• 每个节点（包含叶子）中有一个储存线段的数据结构。若一个线段S的坐标区间包含Int(N)但不包含Int(parent(N))，则节点N中会储存线段S。

题目：

Problem Description

A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.

You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.

战争前夕，一群邪恶的敌舰在外面排成一行准备进攻，我们的指挥官决定使用自主研发的秘密武器摧毁他们。敌军的每艘战舰都标记了一个生命值，每次发射秘密武器，敌舰的生命值会减少为原来开根号值。我们的指挥官现在想计算出武器的效果，所以他寻求你的帮助，让你来计算一个连续区间的战舰的总生命值。

Notice that the square root operation should be rounded down to integer.

注意开根号后需要floor到整值。

Input

The input contains several test cases, terminated by EOF.

For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)

The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 263.

The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)

For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.

输入包含多个用例，使用EOF结束。

对于每个用例，第一行是一个整数N，表示有N个战舰。

第二行包含N个整数Ei，表示每艘战舰的生命值，所有的生命值加起来少于2的63次方。

下面一行包含整数M，表示有多少次攻击或者询问。

接下来有M行，每行包括三个整数T、X、Y。

T=0 表示使用秘密武器攻击一次，X和Y表示区间。

T=1 表示指挥官询问区间X和Y敌舰的生命值总和。

Output

For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.

Sample Input

10

1 2 3 4 5 6 7 8 9 10

5

0 1 10

1 1 10

1 1 5

0 5 8

1 4 8

Sample Output

Case #1:

19

7

6

解题说明：典型的线段树操作，在理解线段树概念的基础上再来看此题，能够很好的加深理解。

G++：690ms

#include <stdio.h>
#include <math.h>
#define MAXN 100010

//线段树节点
typedef struct node_s {
    long long sum;
    int l, r, len;
} node_t;

static node_t tree[MAXN * 4];

// 更新统计总生命值
void update_sum(int now) {
    //总值为左右孩子的值的和
    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
}

//构建区间[l,r]
void build(int now, int l, int r) {
    tree[now].l = l;
    tree[now].r = r;
    tree[now].len = tree[now].r - tree[now].l + 1;

    //输入生命值
    if (tree[now].l == tree[now].r) {
        scanf("%lld", &tree[now].sum);
        return;
    }

    //中间位置
    int mid = (tree[now].l + tree[now].r) >> 1;

    //更新左右孩子
    build(now << 1, l, mid);
    build(now << 1 | 1, mid + 1, r);

    //计算该节点的值
    update_sum(now);
}

//被秘密武器攻击后，需要更新敌舰的生命值
void update(int now, int l, int r) {
    //说明生命值全部是1，无需更新
    if (tree[now].sum == tree[now].len) return;

    //更新战舰生命值
    if (tree[now].l == tree[now].r) {
        tree[now].sum = (long long)sqrt((double)tree[now].sum);
        return;
    }

    int mid = (tree[now].l + tree[now].r) >> 1;

    if (r <= mid) update(now << 1, l, r);
    else if (l > mid) update(now << 1 | 1, l, r);
    else { update(now << 1, l, mid); update(now << 1 | 1, mid + 1, r); }

    update_sum(now);
}

//查询区间[l,r]的总生命值
long long query(int now, int l, int r) {
    //如果刚好是这个区间，直接返回，线段树的性能优势在于此
    if (tree[now].l == l && tree[now].r == r)
        return tree[now].sum;

    int mid = (tree[now].l + tree[now].r) >> 1;

    if (r <= mid) return query(now << 1, l, r);
    else if (l > mid) return query(now << 1 | 1, l, r);

    //在两个区间的情况
    return query(now << 1, l, mid) + query(now << 1 | 1, mid + 1, r);
}

int main() {
    int size, query_count;

    int case_num = 0;

    while (~scanf("%d", &size)) {
        printf("Case #%d:\n", ++case_num);
        build(1, 1, size);
        scanf("%d", &query_count);

        for (int i = 1; i <= query_count; i++) {
            int T, X, Y;
            scanf("%d%d%d", &T, &X, &Y);

            //交换大小
            if (X > Y)
                X ^= Y, Y ^= X, X ^= Y;

            //T=0表示攻击，攻击后需要更新生命值
            //T=1表示查询，获取区间的总生命值
            if (T == 0)
                update(1, X, Y);
            else
                printf("%lld\n", query(1, X, Y));
        }
        printf("\n");
    }
}