C语言树状数组的实例详解

C语言树状数组的实例详解

最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^

首先她的常数比线段树小,其次她的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=)

所以熟练掌握她是非常有必要的。。

关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了

1,单点修改,求区间和

#define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y
void Update(int i,int v) // 初始化与单点修改
{
  while(i <= n)
  {
    c[i] += v ;
    i += lowbit(i) ;
  }
}

inline int Sum(int i)  // 区间求和
{
  int res = 0 ;
  while(i > 0)
  {
    res += c[i] ;
    i -= lowbit(i) ;
  }
  return res ;
}

2,区间修改,单点查询

这里要用到差分的思想

创建一个差分数组c[],令c[i] = a[i] - a[i-1] (a[i] 表示原本的第i个数)

则a[i] = ( a[i] - a[i-1] ) + ( a[i-1] - a[i-2] ) + ...... + ( a[2] - a[1] ) +a[1]

= c[i] + c[i-1] + ...... + c[2] + c[1]

所以单点查询变成了区间求和

那么区间修改怎么办呢 ?

我们看这样一个例子:

a 1 3 4 5 7 10

c 1 2 1 1 2 3

若我们令区间[2,4]加2,则

a 1 5 6 7 9 10

c 1 4 1 1 2 1

我们可以发现只有c[2]和c[5]的数值改变了,其实原理也很好想,区间内的前后元素差是不变的,只有(区间第一个元素与前一个元素的差) 和 (区间后第一个元素与区间末尾元素的差) 改变了。所以区间修改问题变成了单点修改问题。

  for(int i=1;i<=n;i++)
  {
    a[i] = read() ;
    Update(i,a[i]-a[i-1]);
  }
/*  int x=0,y=0;    // 注释掉的内容是空间上的优化(初学者建议先跳过)
  for(int i=1;i<=n;i++)
  {
    if(i%2)
    {
      x = read() ;
      Update(i,x-y);
    }
    else
    {
      y = read() ;
      Update(i,y-x) ;
    }
  } */
  int ii ;
  int k,x,y;
  for(int i=1;i<=m;i++)
  {
    ii = read() ;
    if(ii == 1)
    {
      x = read() ; y = read() ; k = read() ;
      Update(x,k);
      Update(y+1,-k);
    }
    if(ii == 2)
    {
      x = read() ;
      printf("%d\n",Sum(x));
    }
  }

(洛谷有对应的模板题 P3374 与 P3368)

上述就是树状数组最基础的两个应用,日后更深入的学习后再来更新。

如有疑问请留言或到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • 必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • C语言单链表实现多项式相加

    本文实例为大家分享了C语言单链表实现多项式相加的具体代码,供大家参考,具体内容如下 //多项式的相加和相乘 #include<stdio.h> #include<stdlib.h> #pragma warning(disable:4996)//兼容scanf typedef struct node { int coef; int expon; struct node* link; }Polynode,*Polynomial; Polynomial InsertPolyLinklis

  • C语言实现的学生选课系统代码分享

    好久没玩过C语言了,上一次还是在大二的时候...废话不多说,这里有一个C语言实现的学生选课系统代码,分享给大家,具体如下: #include<stdio.h> #include<stdlib.h> int N1,N2,kk1,kk2,kk3; struct couse * head1; struct student * head2; struct couse//课程信息结构体 { int num1; char name1[20]; int score; int nelepeo; /

  • linux下c语言的多线程编程

    我们在写linux的服务的时候,经常会用到linux的多线程技术以提高程序性能 多线程的一些小知识: 一个应用程序可以启动若干个线程. 线程(Lightweight Process,LWP),是程序执行的最小单元. 一般一个最简单的程序最少会有一个线程,就是程序本身,也就是主函数(单线程的进程可以简单的认为只有一个线程的进程) 一个线程阻塞并不会影响到另外一个线程. 多线程的进程可以尽可能的利用系统CPU资源. 1创建线程 先上一段在一个进程中创建一个线程的简单的代码,然后慢慢深入. #incl

  • C语言链表实现贪吃蛇游戏

    阅读学习了源代码,并做了简单的注释和修改,里面只用了链表数据结构,非常适合C语言入门者学习阅读. 程序可在VS2013下编译运行. #include<stdio.h> #include<time.h> #include<windows.h> #include<stdlib.h> #define U 1 #define D 2 #define L 3 #define R 4 //蛇的状态,U:上 :D:下:L:左 R:右 typedef struct SNAK

  • C语言树状数组的实例详解

    C语言树状数组的实例详解 最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小,其次她的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=) 所以熟练掌握她是非常有必要的.. 关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了 1,单点修改,求区间和 #define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y void Update(int i,int v)

  • C语言中联合体union的实例详解

     C语言中联合体union的实例详解 1.定义: union(int i, short s, char c) un; un.i = 3; printf("i=%d",un.i); printf("length = %d\n",sizeof(un);//==4,有最大的变量来决定 2.相当与java里的List T类型 3.数据交换 void swap(int *p , int *q){ int temp = *p; *p = *q; *q = temp; } 4.打

  • C语言实现“幸运数”的实例详解

    C语言实现"幸运数"的实例详解 1.题目: 标题:幸运数 幸运数是波兰数学家乌拉姆命名的.它采用与生成素数类似的"筛法"生成. 首先从1开始写出自然数1,2,3,4,5,6,-. 1 就是第一个幸运数. 我们从2这个数开始.把所有序号能被2整除的项删除,变为: 1 _ 3 _ 5 _ 7 _ 9 -. 把它们缩紧,重新记序,为: 1 3 5 7 9 -. .这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去.注意,是序号位置,不是那个数本身能否被3整除!

  • C语言数据输入与输出实例详解

    C语言数据输入与输出实例详解 1 概论 C语言提供了跨平台的数据输入输出函数scanf()和printf()函数,它们可以按照指定的格式来解析常见的数据类型,例如整数,浮点数,字符和字符串等等.数据输入的来源可以是文件,控制台以及网络,而输出的终端可以是控制台,文件甚至是网页. 2 数据输出 从第一个c语言程序中,就使用了跨平台的库函数printf实现将一段文字输出到控制台,而实际上,printf()不仅可以将数据按照指定的格式输出到控制台,还可以是网页或者是指定的文件中,printf()函数执

  • C语言线性表顺序存储结构实例详解

    C语言线性表顺序存储结构实例详解 1. 什么是顺序存储结构? 用一段地址连续的存储单元依次存储线性表的数据元素. 2.线性表的顺序存储结构 #include<stdio.h> #include<stdlib.h> #define Max 80 //存储空间初始分配量 #define Increment 10 //存储空间分配增量 typedef struct { int *elem; // 存储空间基地址,此处为int型,视情况而定 int length; // 元素表当前长度 i

  • Kotlin 语言中调用 JavaScript 方法实例详解

    Kotlin 语言中调用 JavaScript 方法实例详解 Kotlin 已被设计为能够与 Java 平台轻松互操作.它将 Java 类视为 Kotlin 类,并且 Java 也将 Kotlin 类视为 Java 类.但是,JavaScript 是一种动态类型语言,这意味着它不会在编译期检查类型.你可以通过动态类型在 Kotlin 中自由地与 JavaScript 交流,但是如果你想要 Kotlin 类型系统的全部威力 ,你可以为 JavaScript 库创建 Kotlin 头文件. 内联 J

  • C语言中二级指针的实例详解

    C语言中二级指针的实例详解 用图说明 示例代码: #include <stdio.h> int main(int argc, const char * argv[]) { // int a = 5; int *p1 = &a; //-打印地址-----地址相同--------------- printf("&a = %p\n", &a);// printf("p1 = %p\n", p1);// int **p2 = &p

  • C语言中调用Swift函数实例详解

    C语言中调用Swift函数实例详解 在Apple官方的<Using Swift with Cocoa and Objectgive-C>一书中详细地介绍了如何在Objective-C中使用Swift的类以及如何在Swift中使用Objective-C中的类.在后半部分也介绍了如何在Swift中使用C函数,不过对于如何在C语言中使用Swift函数却只字未提.这里我就为大家分享一下如何在C语言中调用Swift函数. 我们首先要知道的是,所有Swift函数都属于闭包.其次,Swift函数的调用约定与

  • 数据结构之数组Array实例详解

    数据结构之数组Array实例详解 数组Array 基本操作 Status InitArray(int dimm,...)//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK Status DestroyArray() //销毁数组A Status Locate(va_list ap,int &off) //若ap指示的各下标值合法,则求出该元素在A中相对地址off Status Value(ElemType &e,...) //A是n维数组,e为元素变量,随后是n个下标值.

  • ajax响应json字符串和json数组的实例(详解)

    最近上班太忙,晚上抽空整理一下ajax请求中,后台返回json字符串和json数组的场景,以及前台的处理示例. 直接看代码. json字符串的后台响应 package com.ajax; import java.io.IOException; import java.io.PrintWriter; import javax.servlet.ServletException; import javax.servlet.annotation.WebServlet; import javax.serv

随机推荐