树状数组的基础知识
2021-04-26 10:30
标签：ack 基础知识 back 最小 技术 owb 特点 ima 树根 树状数组的原理是：任意一个数都能被一个独有的二进制数表示。基于此，对于一个区间[1,x]，树状数组将其分解为logx个区间，从而快速询问区间和。 树状数组的每个子区间的共同特点是：若区间结尾为R，则区间长度就等于R的“二进制分解下”最小的2的次幂，设为lowbit(R)。 lowbit(R)表示的是区间长度。 lowbit的求法： 举个例子：求7的lowbit值：7的二进制分解为111，其中最低一位出现1的位为第一位，所以7的lowbit值即为1。 求6的lowbit值：6的二进制分解为110，其中最低一位出现1的位为第二位，所以6的lowbit值为10即2。 求8的lowbit值：8的二进制分解为100，其中最低一位出现1的位为第三位，所以8的lowbit值为100即8。 树状数组的形状： 其中，A数组存储的是原数组，C数组（即树状数组）存储的是[x-lowbit(x)+1,x]中所有数的和（如6的lowbit值为2，则C[6]存储的 便是A[6-2+1,6]的值即为A[5]+A[6]的值）。 树状数组的性质： ①每个内部结点c[x]保存以它为根的子树中所有子节点的和。 ②每个内部结点c[x]的子节点个数等于lowbit(x)的大小。 ③除树根外，每个内部节点c[x]的父节点是c[x+lowbit(x)]。 ④树的深度为O(logN)。 以上便是树状数组的基本知识。 树状数组的基础知识 标签：ack 基础知识 back 最小 技术 owb 特点 ima 树根 原文地址：https://www.cnblogs.com/qianr/p/13253221.html