蓝桥杯刷题 Day5 线段树（树状数组）

蓝桥杯刷题 Day5 线段树

前言

今天写牛客网模板题中数据结构的线段树

完整代码

一、树状数组

原题地址: 线段树

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // 输入
        int n = input.nextInt();
        int q = input.nextInt();

        int[] a = new int[n+1]; // 用了最低有效位，数组应扩容

        // 调用线段树类,传入n设定数组范围
        SegmentTree tree = new SegmentTree(n);
        // 初始化树状数组，分层管理
        for (int i = 1; i <= n; i++) {
            a[i] = input.nextInt();
            tree.update(i, a[i]);
        }

        // 处理查询
        while(q-- > 0){
            int op = input.nextInt();
            if(op == 1){
                int i = input.nextInt();
                int k = input.nextInt();
                tree.update(i, k); // 单点更新
            }
            if(op == 2){
                int l = input.nextInt();
                int r = input.nextInt();
                System.out.println(tree.query(r) - tree.query(l - 1)); // 区间求和
            }
        }
    }
}

class SegmentTree{
    private long[] tree; // 存储数组大小

    public SegmentTree(int n){
        tree = new long[n + 1]; // 索引0不使用
    }

    // 单点更新：将k添加到i位置，向上更新所有层级
    public void update(int i, int k){
        while(i < tree.length){
            tree[i] += k;
            i += lowBit(i); // 父节点索引
        }
    }

    // 前缀和查询
    public long query(int index){
        long sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= lowBit(index); // 向左更新区间
        }
        return sum;
    }

    // 计算最低有效位（定位父子节点区间）
    private int lowBit(int x){
        return x & (-x);
    }
}

1. 解题思路

1.1 问题抽象

1. 更新ai
2. 计算区间和

1.2 核心思想

1. 分层管理，多个子节点求和成父节点
2. lowBit()最低有效位

1.2 适用条件：

• 数据量极大（例如10⁶级别）
• 需要频繁的单点更新和前缀和/区间和查询

1.3典型应用：

• 实时数据监控（股票、物流）
• 动态排名系统（游戏积分榜）
• 算法竞赛中的优化题（如逆序对统计）

2. 拆解代码

2.1 主函数

2.1.1 输入以及初始化

 Scanner input = new Scanner(System.in);
        // 输入
        int n = input.nextInt();
        int q = input.nextInt();

        int[] a = new int[n+1]; // 用了最低有效位，数组应扩容

        // 调用线段树类,传入n设定数组范围
        SegmentTree tree = new SegmentTree(n);
        // 初始化树状数组
        for (int i = 1; i <= n; i++) {
            a[i] = input.nextInt();
            tree.update(i, a[i]);
        }

2.1.2 处理查询

// 处理查询
        while(q-- > 0){
            int op = input.nextInt();
            if(op == 1){
                int i = input.nextInt();
                int k = input.nextInt();
                tree.update(i, k); // 单点更新
            }
            if(op == 2){
                int l = input.nextInt();
                int r = input.nextInt();
                System.out.println(tree.query(r) - tree.query(l - 1)); // 区间求和
            }

2.2 SegmentTree类

2.2.1 初始化数组以及最低有效位

  private long[] tree; // 存储数组大小

    public SegmentTree(int n){
        tree = new long[n + 1]; // 索引0不使用
    }

// 计算最低有效位（定位父子节点区间）
    private int lowBit(int x){
        return x & (-x);
    }

2.2.2 单点更新与集区间求和

    // 单点更新：将k添加到i位置
    public void update(int i, int k){
        while(i < tree.length){
            tree[i] += k;
            i += lowBit(i); // 父节点索引
        }
    }

    // 前缀和查询，1~index
    public long query(int index){
        long sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= lowBit(index); // 找前驱区间
        }
        return sum;
    }

二、 题后收获

3.1 知识点

1. 最低有效位：对于二进制来说，保留最右侧的1，其余均为0；