树状数组模板

我不是女神ヾ 2022-08-27 10:42 167阅读 0赞

胡说：树状数组和堆都是我特别喜欢的数据结构，对我来说，编起来的节奏就是和别的不一样，如果把编程说是一首歌，这两种就是明朗轻快的类型。

题目：问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间\[x,y\]内格子权值和，p=3时表示求区间\[x,y\]内格子最大的权值。

输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。

样例输入

4 3  
1 2 3 4  
2 1 3  
1 4 3  
3 1 4

样例输出

6  
3

数据规模与约定

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

题目链接：[点击打开链接][Link 1]

标准的树状数组题，大家可能要注册才能看到题。。当然你可以直接看题目，后来用方法去做其他oj上的题。

因为还不适应大量文字解释代码，我就不讲解每段代码的含义了，基本的原理其他大神的博客里都有，我还是比较喜欢我的代码，通俗易懂。。（其实就是菜）

看完原理之后其实只要一张图就够所有的分析了，日后回忆起来看到图也都会了，所有的树状数组都由lowbit(x)而来，不知道是谁发现的，他真是厉害。。看完代码有不明白的，欢迎留言。

![Center][]

#include <iostream>
    #include <cstring>
    using namespace std;
    
    int i,n,m,a[100001],c[100001],idx[100001];
    
    int lowbit(int x)
    {
        return (x&(-x));
        }
    
    //To c 求c数组
    void Findc()
    {
        int i,j;
        for (i=1;i<=n;i++)
        {
            for (j=i;j<=n;j+=lowbit(j))
                c[j]+=a[i];
            }
    }
    
    //Change  修改一个数组元素后的操作
    void Modify(int k,int d)
    {
         int i,j;
         //增值 
         for (i=k;i<=n;i+=lowbit(i))
                c[i]+=d;
         a[k]=a[k]+d;
         //最大值
         for (i=k;i<=n;i+=lowbit(i))
         {
             idx[i]=a[i];
             for (j=1;j<lowbit(i);j<<=1)
             {
                 idx[i]=max(idx[i-j],idx[i]);
                 }
             } 
         }
    
    //bigger
    int max(int a,int b)
    {
        if (a>b) return a;
        return b;
        }
        
    //Sum   求区间和
    int Sum(int n)
    {
         int s=0;
         while (n>=1)
         {
               s+=c[n];
               n=n-lowbit(n); 
               }
         return s;
         }
    //prefind  预处理区间最大值
    void Premax()
    {
         int i,j;
         memset(idx,0,sizeof(idx));
         for (i=1;i<=n;i++)
         {
             for (j=i;j<=n;j+=lowbit(j))
                 idx[j]=max(idx[j],a[i]);
             }
    }
             
    //Max   求区间最大值，重点是划分区间
    void FindMax(int x,int y)
    {
         int i,j,k;
         //query
         k=y;
         int Max=-1000;
         while (1)
         {
               if (k<x) break;
               if (k-lowbit(k)+1>=x)
               {
                  Max=max(Max,idx[k]);
                  k=k-lowbit(k);
                  }
                  else
                  {
                      if (k<x) break;
                      Max=max(Max,a[k]);
                      k--;
                      if (k<x) break;
                      }
               }
         cout << Max << endl;
         }
    
    int main()
    {
        int choice,x,y;
        cin >> n >> m;
        for (i=1;i<=n;i++)
            cin >> a[i];
        Premax();
        Findc();
        while (m--)
        {
              cin >> choice;
              switch (choice)
              {
              case 1: cin >> x >> y;
                      Modify(x,y-a[x]);
                      break;
              case 2: cin >> x >> y;
                      cout << Sum(y)-Sum(x-1) << endl;
                      break;
              case 3: cin >> x >> y;
                      FindMax(x,y);
                      break;
                      }
              } 
        return 0;
        }

[Link 1]: http://lx.lanqiao.org/problem.page?gpid=T18
[Center]: /images/20220824/2c7c0c05c94e4a95931344cba6bb1a7c.png