• 20220725树状数组入门反思

    最近学习了树状数组和线段树，图论一点点啃吧，然后首先介绍一下树状数组的原理：

     借用acwing一老哥的题解了。

    树状数组的本质思想是使用树结构维护”前缀和”，从而把时间复杂度降为O(logn)。

    对于一个序列，对其建立如下树形结构：

    每个结点t[x]保存以x为根的子树中叶结点值的和
    每个结点覆盖的长度为lowbit(x)
    t[x]结点的父结点为t[x + lowbit(x)]
    树的深度为log2n+1

    lowbit操作的代码是

    return x & -x;

    这样可以返回第一个非零位的数， 比如 10001100的lowbit就是100

    对于一个节点，如果去找他的父节点就是x + lowbit（x）父节点可以继续往上找。

    然后介绍一下他的操作

    首先是add(x, c)

    这里举个例子

     我们上边说了， 是基于lowbit操作向上操作，每个区间的长度也是lowbit（x）。

    所以以

    add(3, 5)为例：
    在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确。时间复杂度为O(logn)，注意这个递归的过程。

    void add(int x, int k)
    {
        for(int i = x; i <= n; i += lowbit(i))
            t[i] += k;
    }

    第二个操作是求和，求1到x的和，

    我们只需要以add反过来操作就好

    int ask(int x)
    {
        int sum = 0;
        for(int i = x; i; i -= lowbit(i))
            sum += t[i];
        return sum;
    }

     以上素材来自小破站

    树状数组可以解决的问题有；

     修改某个点，查询前缀和，再根据这个进行改变。

    242. 一个简单的整数问题

    给定长度为 NN 的数列 AA，然后输入 MM 行操作指令。

    第一类指令形如 C l r d，表示把数列中第 l∼rl∼r 个数都加 dd。

    第二类指令形如 Q x，表示询问数列中第 xx 个数的值。

    对于每个询问，输出一个整数表示答案。

    输入格式

    第一行包含两个整数 NN 和 MM。

    第二行包含 NN 个整数 A[i]A[i]。

    接下来 MM 行表示 MM 条指令，每条指令的格式如题目描述所示。

    输出格式

    对于每个询问，输出一个整数表示答案。

    每个答案占一行。

    数据范围

    1≤N,M≤1051≤N,M≤105,
    |d|≤10000|d|≤10000,
    |A[i]|≤109|A[i]|≤109

    输入样例：

    1. 10 5
    2. 1 2 3 4 5 6 7 8 9 10
    3. Q 4
    4. Q 1
    5. Q 2
    6. C 1 6 3
    7. Q 2

    输出样例：

    1. 4
    2. 1
    3. 2
    4. 5

     首先存在单点修改操作，另外查询某个点的数值就相当于ask(n)

    因为我们用树状数组储存的是差分，前n项的和就等于第n项的数值

    如果们想要加的话就在add(i, a[i] - a[i - 1])

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 2e5 + 10;
    7. int tr[N];
    8. int w[N];
    9. int n, m;
    10.  
    11. int lowbit(int x) {
    12.     return x & -x;
    13. }
    14.  
    15. void add(int x, int c) {
    16.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    17. }
    18.  
    19. long long ask(int x) {
    20.     long long ans = 0;
    21.     for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    22.     return ans;
    23. }
    24.  
    25. int main() {
    26.     scanf("%d%d", &n, &m);
    27.     for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    28.     for (int i = 1; i <= n; i++) add(i, w[i] - w[i - 1]);
    29.     
    30.     while (m --) {
    31.         char op[2];
    32.         int l, r, c;
    33.         scanf("%s%d", op, &l);
    34.         if (*op == 'Q') {
    35.             printf("%lld\n", ask(l));
    36.         } else {
    37.             scanf("%d%d", &r,  &c);
    38.             add(l, c);
    39.             add(r + 1, -c);
    40.         }
    41.     }
    42.     
    43.     return 0;
    44. }

     这是第一道题目，区间修改单点查询， 运用的差分的知识，通过单点查询，区间求和实现差分的功能

    243. 一个简单的整数问题2

    给定一个长度为 NN 的数列 AA，以及 MM 条指令，每条指令可能是以下两种之一：

    1. C l r d，表示把 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 都加上 dd。
    2. Q l r，表示询问数列中第 l∼rl∼r 个数的和。

    对于每个询问，输出一个整数表示答案。

    输入格式

    第一行两个整数 N,MN,M。

    第二行 NN 个整数 A[i]A[i]。

    接下来 MM 行表示 MM 条指令，每条指令的格式如题目描述所示。

    输出格式

    对于每个询问，输出一个整数表示答案。

    每个答案占一行。

    数据范围

    1≤N,M≤1051≤N,M≤105,
    |d|≤10000|d|≤10000,
    |A[i]|≤109|A[i]|≤109

    输入样例：

    1. 10 5
    2. 1 2 3 4 5 6 7 8 9 10
    3. Q 4 4
    4. Q 1 10
    5. Q 2 4
    6. C 3 6 3
    7. Q 2 4

    输出样例：

    1. 4
    2. 55
    3. 9
    4. 15

    这道题目用了一个转化的过程，就是我们首先用第一个差分求的每一位上的数字，然后再对整体进行求前缀和

     这样的话就ok了

    我们的树状数组还是用来维护差分的，然后用前缀和再去实现区间求和的过程

    注意这一步，是用来转化成前缀和的，我们维护了两个前缀和，一个是d[i], 另外一个是 id[i]

    code：

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010;
    6.  
    7. long long tr1[N];
    8. long long tr2[N];
    9. int a[N];
    10. int n, m;
    11.  
    12. int lowbit(int x) {
    13.     return x & -x;
    14. }
    15.  
    16. void add(long long tr[], int x, long long c) {
    17.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    18. }
    19.  
    20. long long sum(long long tr[], int x) {
    21.     long long ans = 0;
    22.     for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    23.     return ans;
    24. }
    25.  
    26. long long query(int x) {
    27.     return sum(tr1, x) * (x + 1) - sum(tr2, x);
    28. }
    29.  
    30. int main() {
    31.     scanf("%d%d", &n, &m);
    32.     for (int i = 1; i <= n; i++) {
    33.         scanf("%d", &a[i]);
    34.         int b = a[i] - a[i - 1];
    35.         add(tr1, i, b);
    36.         add(tr2, i, (long long)b * i);
    37.     }
    38.     
    39.     while (m --) {
    40.         char op[2];
    41.         int l, r, d;
    42.         scanf("%s%d%d", op, &l, &r);
    43.         if (*op == 'Q') {
    44.             printf("%lld\n", query(r) - query(l - 1));
    45.         } else {
    46.             scanf("%d", &d);
    47.             add(tr1, l, d), add(tr2, l, (long long)d * l);
    48.             add(tr1, r + 1, -d), add(tr2, r + 1, (long long)(r + 1) * -d);
    49.         }
    50.     }
    51.     
    52.     return 0;
    53.     
    54.    
    55.     return 0;
    56. }

    注意开龙龙啊， 数据很大

    214 楼兰图腾

    在完成了分配任务之后，西部 314314 来到了楼兰古城的西部。

    相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。

    西部 314314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 nn 个点，经测量发现这 nn 个点的水平位置和竖直位置是两两不同的。

    西部 314314 认为这幅壁画所包含的信息与这 nn 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)(1,y1),(2,y2),…,(n,yn)，其中 y1∼yny1∼yn 是 11 到 nn 的一个排列。

    西部 314314 打算研究这幅壁画中包含着多少个图腾。

    如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1≤iyj,yjyj,yjV 图腾;

    如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1≤iykyiyk，则称这三个点构成 ∧ 图腾;

    西部 314314 想知道，这 nn 个点中两个部落图腾的数目。

    因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

    输入格式

    第一行一个数 nn。

    第二行是 nn 个数，分别代表 y1，y2,…,yny1，y2,…,yn。

    输出格式

    两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。

    数据范围

    对于所有数据，n≤200000n≤200000，且输出答案不会超过 int64int64。
    y1∼yny1∼yn 是 11 到 nn 的一个排列。

    输入样例：

    1. 5
    2. 1 5 3 2 4

    输出样例：

    3 4

     这道题，就是树状数组也可以解决。

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1e06 + 10;
    7. int tr[N], w[N];
    8. int lower[N], upper[N];
    9. int n, m;
    10. int lowbit(int x) {
    11.     return x &-x;
    12. }
    13.  
    14. void add(int x, int c) {
    15.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    16. }
    17.  
    18. long long ask(int x) {
    19.     long long ans = 0;
    20.     for (int i = x; i; i -= lowbit(i)) {
    21.         ans += tr[i];
    22.     }
    23.     return ans;
    24. }
    25.  
    26. int main() {
    27.     scanf("%d", &n);
    28.     for (int i = 1; i <= n; i++) {
    29.         scanf("%d", &w[i]);
    30.     }
    31.     for (int i = 1; i <= n; i++) {
    32.         int b = w[i];
    33.         upper[i] = ask(n) - ask(b);
    34.         lower[i] = ask(b);
    35.         add(b, 1);
    36.     }
    37.     //for (int i = 1; i <= n; i++) cout << upper[i] << ' ' << lower[i] << endl;
    38.     long long ans1 = 0;
    39.     long long ans2 = 0;
    40.     memset(tr, 0, sizeof tr);
    41.     for (int i = n; i; i--) {
    42.         int b = w[i];
    43.         ans1 += (long long)upper[i] * (ask(n) - ask(b));
    44.         ans2 +=  (long long)lower[i] * (ask(b));
    45.         add(w[i], 1);
    46.     }
    47.     printf("%lld %lld", ans1, ans2);
    48.     return 0;
    49. }

    ask(i)就可以求出1到i一共出现过几次，我们每次先处理upper和lower表示左边比他高或者比他低的数量，然后memset一遍，再重新从右到左改一遍upper和lower， 用乘法原理，将结果相加，最后求得总和。

     就是改bug乔难受呜呜呜

    244 谜一样的牛

    有 nn 头奶牛，已知它们的身高为 1∼n1∼n 且各不相同，但不知道每头奶牛的具体身高。

    现在这 nn 头奶牛站成一列，已知第 ii 头牛前面有 AiAi 头牛比它低，求每头奶牛的身高。

    输入格式

    第 11 行：输入整数 nn。

    第 2..n2..n 行：每行输入一个整数 AiAi，第 ii 行表示第 ii 头牛前面有 AiAi 头牛比它低。
    （注意：因为第 11 头牛前面没有牛，所以并没有将它列出）

    输出格式

    输出包含 nn 行，每行输出一个整数表示牛的身高。

    第 ii 行输出第 ii 头牛的身高。

    数据范围

    1≤n≤1051≤n≤105

    输入样例：

    1. 5
    2. 1
    3. 2
    4. 1
    5. 0

    输出样例：

    1. 2
    2. 4
    3. 5
    4. 3
    5. 1

    这道题 ：需要从最后一头牛作为突破口，因为最后一头牛的h[n]表示，在前面的牛中，有h[n]头牛比它矮，即在所有的牛中，有h[n]头牛比他矮，因此最后一牛的高度在所有牛中排第h[n] + 1小。拿第n头牛作为信息点，去掉第n头牛，继续计算第n - 1头牛的高度，再去掉第n - 1头牛，依次类推… 当枚举到第i头牛时，在剩下的牛中高度中排第h[i] + 1小的高度，即是第i头牛的高度。

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 1e05 + 10;
    6. int tr[N];
    7. int w[N], ans[N];
    8. int n;
    9. int lowbit(int x) {
    10.     return x & -x;
    11. }
    12.  
    13. void add(int x, int c) {
    14.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    15. }
    16.  
    17. long long ask(int x) {
    18.     long long ans = 0;
    19.     for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    20.     return ans;
    21. }
    22.  
    23. int main() {
    24.     scanf("%d", &n);
    25.     for (int i = 1; i <= n; i ++) add(i, 1);
    26.     for (int i = 2; i <= n; i++) scanf("%d", &w[i]);
    27.     for (int i = n; i; i--) {
    28.         int l = 1, r = n;
    29.         while (l < r) {
    30.         int mid = l + r >> 1;
    31.             if (ask(mid) >= w[i] + 1) {
    32.                 r = mid;
    33.             } else {
    34.                 l = mid + 1;
    35.             }
    36.         }
    37.         ans[i] = l;
    38.         add(l, -1);
    39.     }
    40.     
    41.     for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    42.     return 0;
    43. }

    结束了，run

  • 相关阅读:
    【MATLAB教程案例48】初识点云——pcshow,pointCloud,pcwrite,pcread,pcdenoise等点云基本操作函数学习
    一道[CSCCTF 2019 Qual]FlaskLight的详解再遇SSTI
    揭秘APP看广告：收益如何稳定？
    1000套web前端期末大作业 HTML+CSS+JavaScript网页设计实例 企业网站制作【建议收藏】
    nodejs+vue+elementui高校师资管理系统开发java python php
    【WSL】SSH 远程连接及宿主机端口转发配置
    Springboot结合Netty对接硬件，实现主动发送报文和接受硬件报文（ModbusRTU或者TCP以及DTU）
    华为云开源低代码引擎 TinyEngine 正式发布
    Datax从mysql同步数据到HDFS
    JAVA 中集合取交集
  • 原文地址：https://blog.csdn.net/beloved_yu/article/details/125987524