Light oj 1080 - Binary Simulation(树状数组区间更新点查询)

题目链接

题意：

    有一字符串只包含0和1，然后又m组操作，I L R是将从L到R的字符进行翻转操作0变为1、1变为0，Q x表示询问第x的字符。

思路：

    我们只需要计算对询问的字符进行了多少次翻转，如果是偶数次，该字符变，否则翻转。对于区间的更新，我们可以使用线段树，不过对于这个题，因为只是对点的查询，而且每个节点的初始值都相同，为0，因此我们可以直接使用树状数组。下面是一个很巧妙的做法，而且很容易理解。

用了树状数组的区间更新 单点查找（一般为单点更新 区间查找）

例如 区间（2,4）加1

则Updata(2,1)   Updata(4+1,-1)

实现了更新（2,4）的值而不改变其他值

求Sum时即可得到某一点的值

//LA 1080 - Binary Simulation
//2013-04-12-18.52
#include <stdio.h>
#include <string.h>

const int maxn = 100010;
char str[maxn];
int n;
int sum[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void change(int x, int v)
{
    while (x <= n)
    {
        sum[x] += v;
        x += lowbit(x);
    }
}

int get(int x)
{
    int s = 0;
    while (x)
    {
        s += sum[x];
        x -= lowbit(x);
    }
    return s;
}

void update(int l, int r)
{
    change(l, 1);
    change(r+1, -1);
}

int main()
{
    int t, m;
    scanf("%d",&t);
    for(int i = 1; i <= t; i++)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%s",&str[1]);
        scanf("%d",&m);
        n =strlen(&str[1]);
        char op;
        int l, r;
        printf("Case %d:\n",i);
        while (m--)
        {
            getchar();
            scanf("%c",&op);
            if (op == 'I')
            {
                scanf("%d %d",&l, &r);
                update(l, r);
            }
            else
            {
                scanf("%d",&l);
                if (get(l)%2 == 1)
                {
                    if (str[l] == '1')
                        puts("0");
                    else
                        puts("1");
                }
                else
                    printf("%c\n",str[l]);
            }

        }
    }
    return 0;
}

这题也可以用线段树来做，个人感觉没有必要，有兴趣的读者可以试试。