【算法题】树状数组

建议点赞收藏关注！
本站友情链接：

树状数组：
可以区间求和、区间最大值、单点修改、快速求区间中点。一般不能区间修改（就这个结构而言）。

区间修改要用线段树。
非要用树状数组进行区间修改，则需要差分数组（也是单点修改、区间求和的数据结构）。

1. lowbit(x)就是从右往左数，'1’所在的最低位
   
2. 树状数组与lowbit的关系
   树状数组利用lowbit存储前缀和。
   例如：idx=[0,1…8]
   0:这里忽略，只占位, index(0)=0
   1: 01 -> lowbit=1
   2: 10-> lowbit=2
   3: 11 -> lowbit=1
   4: 100-> lowbit=3
   5: 101-> lowbit=1
   6: 110-> lowbit=2
   7: 111-> lowbit=1
   8: 1000-> lowbit=4

lowbit=1的有1，3，5，7
lowbit=2的有2，6
lowbit=3的有4
lowbit=4的有8

则得到如下图像
sum of（又称前缀和） 的范围计算为tree[i] = sum(a[i - lowbit(i) + 1],…,a[i])
lowbit可以表示区间的长度.也可以作为指针查询对应的某个tree

3. 题型

#模版
def lowbit(x):
    return x & (-x)
 
# 1、树状数组前缀和
# 求前缀和a[i] + ... + a[x]
# 从x出发，往左走，每次减去lowbit(x)
def query(x, tree):
    """
    :param x:前x项的前缀和
    :param tree:树状数组
    :return:ans 前x项的前缀和
    """
    ans = 0
    while x:
        ans += tree[x]
        x -= lowbit(x)
    return ans
 
 
# 实现单点的更新
# 如果将a[x] + y?
# 从x出发向右走，每次加上lowbit(x),所以经过的点都加上y
def add(x, y, tree, n):
    while x <= n:
        tree[x] += y
        x += lowbit(x)
 
 
n = int(input())
a = [0] + list(map(int, input().split()))#0占位
 
tree = [0] * (n + 1)
# 初始化的过程构造树状数组
for i in range(1, n + 1):
    add(i, a[i], tree, n)

m = int(input())
for _ in range(m):
    op, a, b = map(int, input().split())
    if op == 1:
        add(a, b, tree, n)
    else: #[a,b]的元素和
        print(query(b, tree) - query(a - 1, tree))

单点修改/查询

指定某一个格子x，令x 进行操作：加上或者减去一个特定的值A。

for i in range(m):
    op = list(map(int, input().split()))
    if op[0] == 1:#单点修改
        x, y = op[1], op[2]
        add(x, y - a[x])#新旧两者的差值
        a[x] = y  # 不要忘记这一步
    else:#单点查询
        x = op[1]
        print(a[x])

中点/最值查询

在一个升序数组中，前缀出现次数 >= 数组大小+1的一半的第一个元素，即为中间值。
将入栈元素作为数组下标（类似于桶排序），将其出现次数存入一个数组中，然后求前缀出现次数.

查询[L,R]范围的最大值：
从右往左开始查询,len表示[L,R]的长度,len=R-L+1.当使用tree[x]=[x-lowbit(x)+1,x]之间的最大值,lowbit(x)可以表示区间长度,
如果len>= lowbit（R）,那么tree[R]可以直接取出来比较ans=max(ans,tree[R]).
例如求[4,7]之间的最大值,len=4,lowbit(7)=1，(tree[7]=arr[7]).
如果lowbit（R）>len呢,直接拿arr[R]来比较就行了,ans=max(ans,arr[R]).

s = list()
c = [0 for i in range(100861)]#树状数组 题目范围不超过10^5


def lowBit(x):
    return x & (-x)


def update(x, v):
    i = x
    while i < 100861:
        c[i] += v
        i += lowBit(i)


def getSum(x):
    sum, i = 0, x #sum=0 ,i=x
    while i >= 1:
        sum += c[i]
        i -= lowBit(i)
    return sum


def find():
    left, right, k = 1, 100861, (len(s) + 1) // 2
    while left < right:
        mid = (left + right) // 2
        if getSum(mid) >= k:
            right = mid
        else:
            left = mid + 1
    print(left)


def solve():
    global c, s
    n = int(input())
    for i in range(n):
        command = input().split()
        if command[0][1] == 'u':#push
            s.append(int(command[1]))
            update(int(command[1]), 1)
        elif command[0][1] == 'o':#pop
            if len(s) == 0:
                print("Invalid")
            else:
                update(s[-1], -1)
                print(s[-1])
                s.pop()
        elif command[0][1] == 'e':#median
            if len(s) == 0:
                print("Invalid")
            else:
                find()


if __name__ == "__main__":
    solve()

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>

#define inf 0xffffffff
#define lowbit(i) ((i)&(-(i)))
using namespace std;


const int maxn=100861;

stack<int> s;
int c[maxn];

void update(int x, int v)
{
    for(int i=x; i<maxn; i+=lowbit(i))
        c[i]+=v;
}

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

void find()
{
    int left=0;
    int right=maxn;
    int mid;
    int k=(s.size()+1)>>1;//size_mid
    while(left<right)
    {
        mid=(left+right)>>1;
        if(sum(mid)>=k)
            right=mid;
        else
            left=mid+1;
    }
    printf("%d\n", left);
}

int main()
{
    int n;
    scanf("%d", &n);
    char command[15];
    for(int i=0; i<n; i++)
    {
        scanf("%s", command);
        if(command[1]=='u')//push
        {
            int t;
            scanf("%d", &t);
            update(t, 1);
            s.push(t);
        }
        else
            if(command[1]=='o')//pop
                if(s.size()==0)
                    printf("Invalid\n");
                else
                {
                    update(s.top(), -1);
                    printf("%d\n", s.top());
                    s.pop();
                }
            else
                if(command[1]=='e')//median
                    if(s.size()==0)
                        printf("Invalid\n");
                    else
                        find();
    }
    return 0;
}

区间查询

查询某一个特定的子区间[a, b]中所有元素的元素和。

 print(query(b, tree) - query(a - 1, tree))