@wzq 2016-08-15T02:22:33.000000Z 字数 1902 阅读 847

数据结构

知识点

一些操作介绍

“初始数据”：一开始的数据。
“修改”：对部分数据进行修改。
“查询”：对现有的数据进行查询操作，输出查询结果。
“标记修改”：以修改常数处或logN处，来修改一个长段的值。
“离线查询”：没有修改操作或修改均在查询之前，计算完答案后，最后可以一起输出答案。
“在线查询”：每次询问必须立刻得到结果，不支持离线查询。
“单点修改”：每次只修改一个点的值。
“区间修改”：每次修改一个区间的值。
“单点查询”：询问某个点的值。
“区间查询”：询问某个区间的值。
(9-10一般指在线查询)
“动态维护”：支持动态修改和在线询问。

几种常见的求和问题

无修改的区间求和

给出n个数，有m次询问，每次询问一个区间[xi,yi]的和。
这个问题用前缀和预处理后，每次查询可以O(1)输出结果。

    sum[0]=0;
    for (int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];
    while(m--)
    {
        int x,y; scanf("%d%d",&x,&y);
        printf("%d\n",sum[y]-sum[x-1]);
    }

区间修改的离线查询(询问在修改后)

给出长度为n的序列，m次修改，每次在区间[xi,yi]加上一个数ci，求最后每个数是多少。
活用前缀和的思想，如果现在xi出加上ci，yi +1处减去ci，最后用前缀和扫一遍过去后，就相当于在[xi,yi]上加上ci。

    for (int i=0; i<=n; i++) a[i]=0;
    while(m--)
    {
        int x,y,c; scanf("%d%d%d",&x,&y,&c);
        a[x]+=c; A[y+1]-=c;
    }
    for (int i=1; i<=n; i++) a[i]+=a[i-1];
    for (int i=1; i<n; i++) printf("%d",a[i]);
    printf("%d\n",a[n]);

除了整段同时加一个数外，对于整段加上一个等差数列，我们也可以用类似的方法处理。

给出长度为n的序列，m次修改，每次在区间[xi,yi]加上一个首项是ri,公差是di的等差数列，求最后每个数是多少。
用两个数组，一个记公差di，一个记最终答案。

    for (int i=0; i<=n; i++) d[i]=a[i]=0;
    while(m--)
    {
        int x,y,r,td; scanf("%d%d%d%d",&x,&y,&r,&td);
        d[x]+=td; d[y+1]-=td;
                        //相当于整段加上同一个数
        a[x]+=r-td; a[y+1]-=(y-x)*td+ri;
                         //a[x]加去(首项-公差)，a[y+1]减去末项
    }
    for (int i=1; i<=n; i++)
    {
        d[i]+=d[i-1];
        a[i]+=a[i-1]+d[i];
    }

单点修改的区间查询

给出一个长度为N的序列，有两种操作，一种是单点修改，把某点的值加上某个数ci，一种是询问一个区间[xi,yi]的和。
这个问题，就是典型的树状数组问题。

struct BitTree
{
    int a[maxn],n; // n表示序列长度
    void init(int len) { n=len; memset(a,0,sizeof(int)*(n+2)); }
    void add(int i,int x)  // 单点修改
    {
        for (; i<=n; i+=(i&(-i))) a[i]+=x;
    }
    int que(int i) // 查询[1,i]的和
    {
        int ret=0;
        for (; i; i-=(i&(-i))) a[i]-=x;
        return ret;
    }
};

以上是求和版的树状数组，支持动态单点修改，支持动态查询区间。把xi处的值添加ci，就是调用add(xi,ci)函数，询问1-x的和，就是调用que(x)函数。区间[xi,yi]的和就是que(yi)-que(xi-1)。

区间修改的单点查询

给出长度为n的序列，两种操作，一种在区间[xi,yi]加上一个数ci，另一种是查询当前状态下某个点xi的值。
这个问题和上述的“区间修改的离线查询”非常相似，就是多了一个在线的单点查询。我们考虑同样的方法来做这个问题，每次修改在xi处+ci，在yi +1处-ci。然而每次询问的时候，我们必须从前往后扫一遍才能求得xi的值，这样做修改虽然O(1)，但是查询却是O(n)。
其实，求和求的是前缀和，即1-i的和，修改只是单点修改，这符合树状数组的操作。因此，我们可以用树状数组来动态维护这个前缀和数组，每次修改调用add(xi,ci)和add(yi+1,-ci)，每次查询调用que(xi)即可。修改和查询的时间都是O(logn)。总时间复杂度是O(mlogn)

区间修改的区间查询

这个常规上是线段树，其实树状数组也可以做。